BFS

📖 문제 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 💡 풀이 방식 • 구현, 시뮬레이션, BFS 필요 자료구조 - 4방향 탐색용 배열 - 외부 공기와 접촉한 수 저장용 2차원 int형 배열 air (-1: 외부 공기) - 치즈 수 1. 가장자리는 무조건 공기이므로 (0,0)부터 BFS를 수행해 가장자리(-1)를 표시한다. 2. 치즈(=값이 1)인 곳에서 상하좌우 中 외부 공기(=값이 -1) 갯수를 센다. 3. 외부 공기와 2개 이상 접하면 치즈를 녹인다. 4. 치즈 갯수가 0개가 될 때까지 ..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS / BFS + 그리디 필요 자료구조 - 인접 정점 정보 저장할 ArrayList 배열 - 정점 방문 표시할 boolean형 배열 - 가중치 정보 저장할 long형 배열 1. 배열 a의 전체 합한 값이 0인지 확인한다. 0이 아니라면 -1을 리턴한다. 2. 인접 정보를 저장할 ArrayList 배열을 생성해 인접한 값들 정보를 저장한다. 3. 방문 표시 배열과 DFS를 통해 leaf 노드까지 쭉 탐색했다가 차례대로 올라온다. (탐색 방향 : 위에서 아래) 4. 부모 정점은 자식..

📖 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   💡  풀이 방식• BFS / DFS1. 응시자가 있는 자리 P에서 BFS를 수행한다.- 해당 응시자 위치에서 4방향 탐색 시 격자 범위를 벗어나고, 출발점 P인 경우 탐색하지 않는다.if(!inRange(nx, ny) || (nx == x && ny == y)) continue; - 맨해튼 거리 2 이하인 곳에 또 다른 응시자P가 존재한다면, 거리두기 실패- 맨해튼 거리가 2 미만이고, 빈 테이블이 존재하는 경우, 큐에 다음 탐색 위치를 추가해 마저 탐색한다.if(s[nx].charAt(n..

📖 문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 💡 풀이 방식 • 부분 집합 (백트래킹, 재귀) + BFS 필요 자료구조 [전역변수] - 인구 수 저장용 1차원 int형 배열 - 그래프 정보를 저장하기 위한 그래프 리스트 배열 - 부분 집합용 사용 여부 표시용 1차원 boolean형 배열 - 최솟값 [BFS용] - 방문할 원소를 저장하는 Integer형 큐 - 방문 표시용 1차원 boolean형 배열 (연결되었는지 확인용) [두 그룹에 속한 원소들 저장하고, 차이 저장용] - 구역A 원소들 저장할 Integer형 리스트 -..

📖 문제 23352번: 방탈출 첫줄에 지도의 세로 크기 $N$($1 \le N \le 50$), 가로 크기 $M$($1 \le M \le 50$)이 공백을 두고 주어진다. 둘째 줄부터 $N$줄에 걸쳐 각 방들의 정보 $A$($0 \le A \le 9$)가 공백을 두고 주어진다. www.acmicpc.net 💡 풀이 방식 • BFS 상하좌우로 이동하며 가장 긴 경로 길이인 시작점과 끝점의 합을 구한다. 4방향 탐색 후, 현재 이동 거리가 최대 이동거리보다 길다면 최대 이동거리 len을 변경하고, 시작 방과 끝 방에 적힌 숫자의 합을 구해 최댓값 max와 비교해 갱신한다. if(!flag && now[2] >= len) { // 현재 이동 거리가 최대 이동거리보다 많으면 최대 이동거리 변경 if(now[2]..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • BFS 필요 자료구조 - 노드 간 연결 정보 저장하는 ArrayList 배열 ➜ List[] A - 1과의 거리 저장하는 배열 ➜ int[] dist - 해당 노드 방문했는지 확인용 방문 배열 ➜ boolean[] visited 1. 인접 리스트에 두 노드 간 연결 정보를 양방향으로 저장한다. 2. 1번부터 bfs를 통해 1번 노드로부터 떨어진 거리를 계산한다. - 해당 노드의 정점 中 방문하지 않은 다음 정점을 방문하려고 할 때, 방문 표시와 큐에 다음 정점을 추가하는 것뿐만 아니..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 시뮬레이션 + BFS ① 한 칸 전진해 점수 갱신 → ② 주사위 굴리고 방향 조정 1. 현재 방향으로 한 칸 전진하여 좌표 값을 갱신하고, 해당 칸에서 bfs를 통해 현재 칸에서 얻을 수 있는 점수를 구해 합을 갱신한다. (한 칸 전진 시 격자판을 벗어난 경우, 반대 방향으로 되도록 조정해준다.) 2. 주사위가 놓인 상태를 조정한다. 이를 위해 현재 이동 방향에 맞춰 주사위를 굴리며 보이는 면 배열 dice를 갱신한다. 그리고 나서 주사위 바닥면의 값과 현재 칸의 값을 비교해 ..

📖 문제 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 💡 풀이 방식 • BFS 필요 자료구조 - 2차원 int형 배열 group : 0끼리 그룹화된 배열 정보 저장 - Map ⇒ 각각 다른 그룹으로 나눌 수 있다 (서로소 = 분리 집합) - BFS 통해 그룹 생성 시, 이미 만들어진 그룹에 속한 인덱스는 제외하고 탐색을 진행한다. - 벽(1)인 경우에만 본인 칸과 주변 상하좌우에 존재하는 0의 개수를 센다. (BFS 아니고 탐색 단 한 번) 💥 유의사항 N과 M이 각각 최대 1000이므..

📖 문제 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 💡 풀이 방식 • BFS - 벽 위치를 저장받는 리스트를 생성해 벽 위치를 저장한다. → 나중에 사각형 범위 안에 벽이 있는지 확인할 때 사용하기 위함 - 시작점 (Sr, Sc)에서부터 인접한 상하좌우 칸으로 이동하며 BFS를 수행한다. ┕ 큐에 저장할 값 : (행, 열, 이동 거리) ┕ 현재 점의 위치가 목표 위치 (Fr,Fc)에 도달했다면, 현재까지의 이동 거리를 출력하고 종료한다. ┕ 목적지에 도달하지 못 했다면, 상하좌우를..