백준 17070번 [파이프 옮기기 1](C++)-yes6686- 티스토리

백준 문제 풀이: 17070 [파이프 옮기기 1]

---

문제 링크: https://www.acmicpc.net/problem/17070

문제 설명:

크기 NxN의 격자판에서 파이프를 이동시키며 (1, 1)에서 (N, N)으로 이동할 수 있는 모든 경로의 개수를 구하는 문제입니다. 파이프는 항상 격자판 위에 존재하며, 빈 칸(0)만 이동할 수 있습니다.

파이프의 이동은 다음 규칙을 따릅니다:

• 파이프는 세 가지 방향(가로, 대각선, 세로)으로 이동 가능합니다.
• 가로 방향(1)에서는 오른쪽 또는 대각선으로만 이동 가능합니다.
• 대각선 방향(2)에서는 세 방향 모두(오른쪽, 아래, 대각선) 이동 가능합니다.
• 세로 방향(3)에서는 아래 또는 대각선으로만 이동 가능합니다.
• 대각선 이동 시, 이동할 칸과 그 주변 두 칸이 모두 비어 있어야 합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[17][17];
int n;
int cnt = 0;

void DFS(int x, int y, int dir) {
    if (x > n || y > n || arr[x][y] == 1) return;

    if (dir == 2 && (arr[x - 1][y] == 1 || arr[x][y - 1] == 1)) return;

    if (x == n && y == n) {
        cnt++;
        return;
    }

    if (dir == 1) { // 가로 방향
        DFS(x, y + 1, 1); // 가로
        DFS(x + 1, y + 1, 2); // 대각선
    } else if (dir == 2) { // 대각선 방향
        DFS(x, y + 1, 1); // 가로
        DFS(x + 1, y + 1, 2); // 대각선
        DFS(x + 1, y, 3); // 세로
    } else if (dir == 3) { // 세로 방향
        DFS(x + 1, y, 3); // 세로
        DFS(x + 1, y + 1, 2); // 대각선
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    DFS(1, 2, 1); // 초기 위치 (1, 2)에서 가로 방향 시작
    cout << cnt << '\n';
    return 0;
}

예제

입력:
6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

출력:
13

---

코드 설명

• DFS를 활용한 경로 탐색:
  • 파이프가 가질 수 있는 세 가지 방향(가로, 대각선, 세로)에 따라 DFS를 진행합니다.
  • 다음 칸으로 이동 가능한 조건을 확인한 후, 가능한 방향으로 이동합니다.
• 도착 조건: 파이프가 (N, N)에 도달하면 경로의 개수를 증가시킵니다.
• 가지치기:
  • 이동하려는 칸이 벽이거나, 대각선 이동 시 벽이 있으면 해당 방향으로 이동하지 않습니다.

시간 복잡도

• DFS 탐색으로 모든 가능한 경로를 탐색합니다.
• 최대 크기가 17x17이므로 시간 복잡도는 O(3^(N^2))로 매우 크지만, N이 작기 때문에 해결 가능합니다.

---

결과

코드는 파이프를 옮길 수 있는 모든 경로를 정확히 계산하며, DFS를 활용하여 효율적으로 탐색합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!