핵심 요약
- 백준 17070번(파이프 옮기기 1)은 단순한 경로 탐색이 아닌, ‘방향성(Orientation)’이 상태를 결정하는 까다로운 문제입니다.
- DFS(깊이 우선 탐색)는 직관적이나, N이 커질수록 중복 연산이 지수적으로 증가하여 시간 초과(Time Limit Exceeded)의 원인이 됩니다.
- 3차원 DP를 도입하여
(행, 열, 방향)으로 상태를 정의함으로써, 중복 계산을 획기적으로 제거하고 O(N2) 성능을 확보할 수 있습니다. - 벽(1)이 있을 때 대각선 이동의 특수 조건(3칸 빈 공간)을 DP 점화식에 정확히 반영하는 것이 구현의 핵심입니다.
목차
- 1. 서론: 파이프, 그 참을 수 없는 방향의 복잡함
- 2. [Phase 1] 직관의 영역: DFS와 백트래킹
- 3. [Critical Point] 왜 N=17부터는 위험한가?
- 4. [Phase 2] 공학의 영역: 3차원 DP 설계
- 5. 최종 솔루션 및 코드 분석
- 6. 결론: 알고리즘 선택의 기준
1. 서론: 파이프, 그 참을 수 없는 방향의 복잡함
알고리즘 문제 해결(PS)에서 ‘격자 탐색’은 가장 빈번하게 등장하는 유형 중 하나입니다. 보통은 “A에서 B까지 가는 최단 거리”를 묻거나 “갈 수 있는 경로의 수”를 묻습니다. 이때 우리는 관성적으로 BFS나 DFS를 떠올립니다.
하지만 백준 17070번 ‘파이프 옮기기 1’은 우리의 이런 관성을 비웃듯 ‘방향(Direction)’이라는 제약 조건을 던집니다. 파이프는 가로, 세로, 대각선 중 하나의 상태를 가지며, 현재 어떤 상태이냐에 따라 미래에 취할 수 있는 행동이 달라집니다. 즉, 같은 좌표 (r, c)에 있더라도 가로로 놓여있는지, 세로로 놓여있는지에 따라 ‘다른 상태’로 취급해야 한다는 뜻입니다. 이 미묘한 차이를 어떻게 코드로 구현하느냐가 이 문제의 승패를 가릅니다.
2. [Phase 1] 직관의 영역: DFS와 백트래킹
가장 먼저 시도해볼 수 있는 방법은 문제를 읽는 그대로 구현하는 시뮬레이션 방식입니다. “현재 상태에서 갈 수 있는 곳을 다 가본다”는 전략이죠. 이것이 바로 DFS(깊이 우선 탐색)입니다.
독자님께서 작성하신 코드는 이 DFS의 정석을 보여줍니다. 재귀 함수를 통해 현재 좌표와 방향을 넘겨주고, 이동 가능한지 check 함수로 검사한 뒤 파고듭니다. 코드를 다시 한번 살펴봅시다.
// 독자님의 DFS 코드 (발췌)
static void dfs(int x, int y, int dir) {
if (x==n-1 && y==n-1) cnt++; // 기저 조건: 목적지 도착
else {
// 현재 방향(dir)에 따라 분기 처리
if (dir==0) { // 가로일 때
if (check(x,y+1)) dfs(x,y+1,0); // 가로로 이동
// 대각선 이동 조건 확인...
if (check(x,y+1) && check(x+1,y) && check(x+1,y+1)) {
dfs(x+1,y+1,2);
}
}
// ... (세로, 대각선 로직 생략)
}
}이 코드는 논리적으로 완벽합니다. 가독성이 좋고 구현 실수를 줄일 수 있는 안전한 방법입니다. N이 작다면 말이죠.
3. [Critical Point] 왜 N=17부터는 위험한가?
문제의 조건인 N ≤ 16은 출제자의 ‘자비’입니다. 이 범위를 벗어나는 순간, DFS는 ‘중복 연산의 늪’에 빠지게 됩니다.
지수 시간 복잡도의 공포
격자판의 크기가 커질수록 경로의 수는 폭발적으로 증가합니다. 특정 지점 (10, 10)에 도달하는 방법이 10,000가지가 있다고 가정해 봅시다.
- DFS의 방식: 10,000번의 경로 각각에 대해,
(10, 10)이후의 여정을 매번 처음인 것처럼 다시 탐색합니다. (10, 10)에서 목적지까지 가는 경우의 수가 5,000가지라면, DFS는 이 구간에서만 10,000 × 5,000번의 연산을 수행하게 됩니다.
이를 빅오(Big-O) 표기법으로 환산하면, 최악의 경우 O(3N2)에 가까운 지수 시간이 걸립니다. N=32인 ‘파이프 옮기기 2’ 문제에서 DFS를 돌린다면, 우주가 멸망할 때까지 답을 기다려야 할지도 모릅니다.
4. [Phase 2] 공학의 영역: 3차원 DP 설계
우리는 “과거의 계산 결과를 재사용”해야 합니다. 이를 위해 다이나믹 프로그래밍(DP)을 도입합니다. DP의 핵심은 ‘상태(State) 정의’입니다.
왜 2차원이 아닌 3차원인가?
단순히 dp[row][col]로 정의하면 안 됩니다. (3, 3)에 도착한 파이프가 ‘가로’로 놓여있는 경우와 ‘세로’로 놓여있는 경우는 다음 이동 경로가 완전히 다르기 때문입니다.
- 가로 상태: 오른쪽, 대각선 이동 가능
- 세로 상태: 아래쪽, 대각선 이동 가능
따라서 방향 정보를 차원에 포함시켜야 합니다.
DP[행][열][방향]
= (행, 열) 위치에 파이프 끝이 [방향] 모양으로 놓이는 경우의 수
점화식(Transition)의 유도
DP는 “나는 어디서 왔는가?”를 묻는 과정입니다. 현재 상태를 만들기 위해 가능한 이전 상태들을 모두 더하면 됩니다.
1. 현재 가로(0)로 놓이려면?
바로 왼쪽 칸(i, j-1)에서 파이프 머리를 밀고 들어와야 합니다. 이때, 이전 파이프는 가로(0)였거나 대각선(2)이었어야만 현재 가로로 놓일 수 있습니다. (세로에서는 가로로 못 바꿈)
dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]
2. 현재 세로(1)로 놓이려면?
바로 위쪽 칸(i-1, j)에서 내려와야 합니다. 이전 파이프는 세로(1)였거나 대각선(2)이어야 합니다.
dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]
3. 현재 대각선(2)으로 놓이려면?
왼쪽 위 대각선 칸(i-1, j-1)에서 내려와야 합니다. 대각선 이동은 모든 방향(가로, 세로, 대각선)에서 전환이 가능합니다. 단, 벽 체크 조건이 가장 까다롭습니다. (i, j)뿐만 아니라 (i-1, j)와 (i, j-1)도 모두 비어 있어야 합니다.
dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]
5. 최종 솔루션 및 코드 분석
이 논리를 바탕으로 작성된 최적화 코드는 다음과 같습니다. 반복문을 사용한 Bottom-Up 방식을 채택하여 재귀 호출 오버헤드까지 제거했습니다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] map = new int[n][n];
for(int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// [행][열][방향]
// 0: 가로, 1: 세로, 2: 대각선
// N이 커질 경우를 대비해 long 타입 사용 (Overflow 방지)
long[][][] dp = new long[n][n][3];
// 초기화: (0, 1) 위치에 가로 방향으로 파이프가 놓여 있음
dp[0][1][0] = 1;
for(int i=0; i<n; i++) {
for(int j=2; j<n; j++) { // (0,0), (0,1)은 스킵
if(map[i][j] == 1) continue; // 현재 위치가 벽이면 배치 불가
// 1. 가로 방향 계산 (왼쪽에서 옴)
dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2];
// 첫 행(i=0)에서는 세로, 대각선 이동이 불가능하므로 예외 처리
if(i == 0) continue;
// 2. 세로 방향 계산 (위쪽에서 옴)
dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2];
// 3. 대각선 방향 계산 (왼쪽 위에서 옴)
// 대각선은 본인 칸(i,j) 외에 위쪽(i-1, j)과 왼쪽(i, j-1)도 벽이 없어야 함
if(map[i-1][j] == 0 && map[i][j-1] == 0) {
dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
}
}
}
// 최종 결과: (N-1, N-1)에 도달하는 모든 방향의 경우의 수 합산
long result = dp[n-1][n-1][0] + dp[n-1][n-1][1] + dp[n-1][n-1][2];
System.out.println(result);
}
}6. 결론: 알고리즘 선택의 기준
이번 리포트를 통해 우리는 같은 문제를 바라보는 두 가지 시각을 경험했습니다.
- DFS: 문제의 흐름을 직관적으로 따라가며 빠르게 구현해야 할 때 (N이 작을 때).
- 3차원 DP: 복잡한 상태 의존성이 존재하고, 입력 크기가 커서 성능 최적화가 필수적일 때.
특히 ‘파이프 옮기기’ 문제는 상태(State)에 ‘방향’을 포함시켜야 한다는 DP의 중요한 교훈을 줍니다. 앞으로 격자 문제에서 “상태가 겹치는데 경로가 다르다”는 느낌을 받는다면, 주저 없이 차원을 하나 더 늘려보세요. 그곳에 정답이 있습니다.