BFS 심화, BackTracking
1. 오늘의 학습 흐름
- BOJ 7576 토마토 (다중 출발점 BFS)
- BOJ 17070 파이프 옮기기 (BFS vs DFS 비교)
- BackTracking 개념
- NQueen 문제
- SWEA 3234 준환이의 양팔저울 (BackTracking + 최적화)
2. BOJ 7576 - 토마토 (다중 출발점 BFS)
여러 위치에서 동시에 BFS가 퍼져나가는 문제다. 단일 출발점 BFS와 구조는 동일하지만, 시작 시 익은 토마토를 모두 큐에 넣고 시작한다.
// 입력 받으면서 익은 토마토(1)를 전부 큐에 넣기
for (int i = 0; i < rowN; i++) {
for (int j = 0; j < colN; j++) {
cur = Integer.parseInt(st.nextToken());
map[i][j] = cur;
if (cur == 1) queue.offer(new int[]{i, j}); // 시작점 여러 개
}
}
bfs();시간(날짜)을 세는 방법: 큐의 size()로 현재 레벨의 노드 수를 얻어서 레벨 단위로 처리한다.
static int time;
public static void bfs() {
while (!queue.isEmpty()) {
int size = queue.size(); // 현재 레벨 노드 수
time++; // 하루 경과
for (int k = 0; k < size; k++) { // 이번 레벨 전부 처리
int[] cur = queue.poll();
int r = cur[0], c = cur[1];
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nr >= rowN || nc < 0 || nc >= colN) continue;
if (map[nr][nc] == 0) {
map[nr][nc] = 1;
queue.offer(new int[]{nr, nc});
}
}
}
}
}int size = queue.size()를 for문 조건에 직접 쓰면 안 된다. offer 할 때마다 size가 늘어나서 현재 레벨 이상을 처리하게 된다.
결과 처리: 0이 남아있으면 -1, 없으면 time-1 출력 (시작 시 time을 1로 잡았기 때문에 -1).
3. BOJ 17070 - 파이프 옮기기
파이프를 (N-1, N-1)까지 옮기는 경우의 수를 구하는 문제다. BFS와 DFS 두 버전으로 풀었다.
파이프 방향: 0=가로, 1=세로, 2=대각선
방향별 이동 가능:
가로(0) → 가로(0), 대각(2)
세로(1) → 세로(1), 대각(2)
대각(2) → 가로(0), 세로(1), 대각(2)// 방향별 이동 delta
static int[][] dr = { {0, 1}, {1, 1}, {0, 1, 1} }; // 가로/세로/대각
static int[][] dc = { {1, 1}, {0, 1}, {1, 0, 1} };
public static void dfs(int r, int c, int dir) {
for (int i = 0; i < dr[dir].length; i++) {
int nr = r + dr[dir][i];
int nc = c + dc[dir][i];
if (nr >= N || nc >= N || map[nr][nc] == 1) continue;
// 대각 이동 시 주변 빈 칸 추가 체크
if (i == dr[dir].length - 1 && (map[nr-1][nc] == 1 || map[nr][nc-1] == 1)) continue;
if (nr == N-1 && nc == N-1) { answer++; break; }
int newDir = (dir == 2) ? i : (i == 0 ? dir : 2);
dfs(nr, nc, newDir);
}
}DFS(210ms) vs BFS(524ms): 이 문제는 BFS를 가장한 DFS라는 게 핵심이다. (N-1, N-1)에 도달 가능한 경우의 수를 세는 것이므로 탐색 구조 자체가 DFS와 동일하다. BFS로 풀면 큐에 객체를 계속 생성/Heap 접근해야 해서 오히려 느리다.
4. BackTracking
DFS + "유망하지 않은 경로를 사전에 차단"하는 기법이다.
BackTracking = DFS + 가지치기(Pruning)핵심 개념:
- 유망(Promising): 해답이 될 가능성이 있는가
- 가지치기(Pruning): 유망하지 않으면 더 탐색하지 않고 되돌아감
백트래킹의 효율은 가지치기를 얼마나 잘 설계하느냐에 달려 있다.
void dfs(int depth) {
if (!isPossible()) return; // 가지치기: 유망하지 않으면 즉시 종료
if (depth == N) {
answer++;
return;
}
for (int i = 0; i < N; i++) {
선택(i);
dfs(depth + 1);
선택해제(i);
}
}5. NQueen
NxN 체스판에 N개의 퀸을 서로 공격하지 않게 배치하는 경우의 수를 구하는 문제다. BackTracking의 대표 예제다.
1차원 배열로 표현하는 게 핵심이다. 각 행에 퀸은 하나뿐이므로 col[row] = 열 위치로 저장한다.
static int[] col = new int[N + 1]; // col[i] = i행의 퀸이 놓인 열
public static void setQueens(int rowNo) {
if (rowNo > N) { answer++; return; } // 모든 행 배치 완료
for (int i = 1; i <= N; i++) {
col[rowNo] = i;
if (!isAvailable(rowNo)) { // 유망 체크
setQueens(rowNo + 1);
}
}
}
public static boolean isAvailable(int rowNo) {
for (int k = 1; k < rowNo; k++) {
// 같은 열이거나 대각선 체크
if (col[rowNo] == col[k]
|| Math.abs(col[rowNo] - col[k]) == rowNo - k) return false;
}
return true;
}대각선 체크 원리 (스크린샷 참고):
\방향: 행의 차이 = 열의 차이 →row - k == col[row] - col[k]/방향: 행의 차이 = 열의 차이(반대) →row - k == col[k] - col[row]- 두 경우를 합치면:
Math.abs(col[row] - col[k]) == row - k
6. SWEA 3234 - 준환이의 양팔저울
N개의 추를 순서대로 하나씩 왼쪽/오른쪽에 올리는데, 항상 왼쪽 ≥ 오른쪽이 되는 경우의 수를 구하는 문제다.
버전 1 - 기본 BackTracking (1653ms)
static void dfs(int[] weight, boolean[] check, int left, int right, int depth) {
if (left < right) return; // 가지치기: 오른쪽이 더 무거우면 종료
if (weight.length == depth) { result++; return; }
for (int i = 0; i < weight.length; i++) {
if (check[i]) continue;
check[i] = true;
dfs(weight, check, left + weight[i], right, depth + 1); // 왼쪽에 올리기
dfs(weight, check, left, right + weight[i], depth + 1); // 오른쪽에 올리기
check[i] = false;
}
}버전 2 - BitMask + 수학적 최적화 (692ms)
static void dfs(int idx, int left, int right, int flag, int remain) {
// left가 남은 모든 추의 합보다 크거나 같으면
// 남은 추를 어디 올려도 left >= right 조건이 항상 성립
if ((left << 1) >= total) {
result += 1 << (N - idx); // 남은 추 개수만큼 2^(N-idx) 경우 전부 추가
return;
}
for (int i = 0; i < weight.length; i++) {
if ((flag & (1 << i)) != 0) continue; // BitMask로 방문 체크
dfs(idx + 1, left + weight[i], right, flag | (1 << i), remain - weight[i]);
if (right + weight[i] <= left) { // 오른쪽에 올려도 조건 만족 시에만
dfs(idx + 1, left, right + weight[i], flag | (1 << i), remain - weight[i]);
}
}
}버전 2의 핵심 최적화 두 가지:
1. (left << 1) >= total: left가 전체 합의 절반 이상이면 남은 추를 어디 올려도 항상 left ≥ right. 남은 경우의 수를 2^(N-idx)로 한 번에 더하고 종료.
2. visited 배열 대신 BitMask: flag & (1<<i)로 O(1) 방문 체크.
7. 리뷰
오늘 양팔저울 버전 1(1653ms) vs 버전 2(692ms)를 보면서 가지치기 설계의 중요성을 체감했다.
버전 2에서 (left << 1) >= total이라는 조건 하나가 시간을 절반 이상 줄였다. 이 조건은 "왼쪽이 전체 합의 절반 이상이면 남은 선택은 결과에 영향 없다"는 수학적 사실에서 나온다. BackTracking에서 좋은 가지치기는 알고리즘 실력뿐만 아니라 문제를 수학적으로 분석하는 능력에서 나온다.
파이프 문제에서 "BFS를 가장한 DFS"라는 표현도 인상 깊었다. 알고리즘을 기계적으로 적용하는 게 아니라 "이 문제의 본질이 DFS인가 BFS인가"를 먼저 판단해야 한다.
8. 키워드 정리
BFS BackTracking
9. 내일의 목표
- 코테 준비
