codingtest

17070번 - 파이프 옮기기 1

2026-02-13
6분 분량
JAVA백준

문제 링크

문제 풀이 시간 : 47

문제 요약

  • 크기 N × N 격자에서 파이프를 이동시키는 경우의 수를 구하는 문제
  • 파이프는 항상 2칸을 차지하며, 방향은 총 3가지
  • 시작 상태는 (1,1) ~ (1,2) 가로 방향
  • 파이프의 한쪽 끝이 (N, N) 에 도달하는 모든 경우의 수를 계산

문제 풀이

처음 문제를 읽었을 때는

👉 그래프 탐색 문제처럼 보였고, BFS로 접근하면 되겠다고 생각했다.

상태는 다음 3가지 정보로 정의할 수 있었다.

  • 현재 파이프 끝 좌표 (x, y)
  • 파이프 방향

즉, (x, y, dir) 을 하나의 상태로 보고

큐를 이용해 가능한 모든 이동을 탐색하는 방식이었다.

📌 초기 접근 – BFS 완전 탐색

핵심 아이디어

  • 현재 방향에 따라 이동 가능한 다음 방향이 정해짐
  • 이동 시 필요한 칸들이 모두 0인지 확인
  • (N, N)에 도달하면 경우의 수 증가

초기 코드

java
import java.io.*;
import java.util.*;

public class Main {

    public static int[][] map;
    public static int n;

    // 현재 위치 (x, y), 현재 방향 dir 에서
    // next 방향으로 이동이 가능한지 검사하는 함수
    public static boolean check(int x, int y, int dir, int next) {

        // 현재 가로 방향
        if (dir == 1) {
            // 가로 -> 가로 (오른쪽)
            if (next == 1 && map[x][y + 1] != 1) {
                return true;
            }
            // 가로 -> 대각선
            if (next == 3 &&
                map[x][y + 1] != 1 &&
                map[x + 1][y] != 1 &&
                map[x + 1][y + 1] != 1) {
                return true;
            }
        }

        // 현재 세로 방향
        else if (dir == 2) {
            // 세로 -> 세로 (아래)
            if (next == 2 && map[x + 1][y] != 1) {
                return true;
            }
            // 세로 -> 대각선
            if (next == 3 &&
                map[x][y + 1] != 1 &&
                map[x + 1][y] != 1 &&
                map[x + 1][y + 1] != 1) {
                return true;
            }
        }

        // 현재 대각선 방향
        else if (dir == 3) {
            // 대각선 -> 가로
            if (next == 1 && map[x][y + 1] != 1) {
                return true;
            }
            // 대각선 -> 세로
            if (next == 2 && map[x + 1][y] != 1) {
                return true;
            }
            // 대각선 -> 대각선
            if (next == 3 &&
                map[x][y + 1] != 1 &&
                map[x + 1][y] != 1 &&
                map[x + 1][y + 1] != 1) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        // 외곽을 벽으로 처리하기 위해 여유 공간을 둠
        map = new int[n + 2][n + 2];

        StringTokenizer st;
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = st.nextToken().charAt(0) - '0';
            }
        }

        // 경계 처리
        for (int i = 0; i <= n + 1; i++) {
            map[i][0] = map[i][n + 1] = 1;
            map[0][i] = map[n + 1][i] = 1;
        }

        Queue<int[]> q = new ArrayDeque<>();
        // 시작 상태: (1,2), 가로 방향
        q.add(new int[]{1, 2, 1});

        int ans = 0;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int x = now[0];
            int y = now[1];
            int dir = now[2];

            // 도착 지점
            if (x == n && y == n) {
                ans++;
                continue;
            }

            // 방향에 따라 가능한 이동
            switch (dir) {
                case 1: // 가로
                    if (check(x, y, 1, 1))
                        q.add(new int[]{x, y + 1, 1});
                    if (check(x, y, 1, 3))
                        q.add(new int[]{x + 1, y + 1, 3});
                    break;
                case 2: // 세로
                    if (check(x, y, 2, 2))
                        q.add(new int[]{x + 1, y, 2});
                    if (check(x, y, 2, 3))
                        q.add(new int[]{x + 1, y + 1, 3});
                    break;
                case 3: // 대각선
                    if (check(x, y, 3, 1))
                        q.add(new int[]{x, y + 1, 1});
                    if (check(x, y, 3, 2))
                        q.add(new int[]{x + 1, y, 2});
                    if (check(x, y, 3, 3))
                        q.add(new int[]{x + 1, y + 1, 3});
                    break;
            }
        }

        System.out.println(ans);
    }
}

❌ BFS 접근의 문제점

  • 같은 상태를 여러 번 탐색
  • 경우의 수가 기하급수적으로 증가
  • N이 작아도 메모리 / 시간 비효율

👉 실제로는 통과는 하지만,

불필요한 상태 탐색이 너무 많다는 점이 문제였다.

post image

🔥 개선 아이디어 – DP로 상태 누적하기

문제를 다시 보니,

👉 이 문제는 전형적인 DP 문제였다.

  • (i, j) 위치에
  • 어떤 방향의 파이프가 도착하는 경우의 수만 알면 된다
  • 그 이전 경로는 중요하지 않다

💡 DP 정의

plain text
dp[dir][i][j]
  • (i, j)에 파이프 끝이 위치하고
  • dir 방향으로 놓여 있는 경우의 수

방향 인덱스:

  • 0 : 가로
  • 1 : 세로
  • 2 : 대각선

🔄 점화식 개념

  • 가로 → 가로, 대각선
  • 세로 → 세로, 대각선
  • 대각선 → 가로, 세로, 대각선

👉 이동 가능 여부만 체크해서 누적

⏱️ 시간 복잡도

  • N ≤ 16
  • 모든 칸 × 3방향

👉 O(N²)

BFS보다 훨씬 안정적이고 빠르다.

최종 코드

java
import java.io.*;
import java.util.*;

public class Main {

    // 집 상태를 저장할 지도
    // 0 : 빈 칸, 1 : 벽
    public static int[][] map;
    public static int n;

    /**
     * 현재 파이프 끝 좌표 (x, y),
     * 현재 방향 dir 에서
     * next 방향으로 이동이 가능한지 확인하는 함수
     *
     * dir / next
     * 1 : 가로
     * 2 : 세로
     * 3 : 대각선
     */
    public static boolean check(int x, int y, int dir, int next) {

        // 현재 파이프가 가로 방향일 때
        if (dir == 1) {

            // 가로 -> 가로 (오른쪽으로 한 칸)
            // (x, y+1) 칸만 비어 있으면 됨
            if (next == 1 && map[x][y + 1] != 1) {
                return true;
            }

            // 가로 -> 대각선
            // 오른쪽, 아래, 오른쪽 아래 총 3칸이 비어 있어야 함
            if (next == 3 &&
                map[x][y + 1] != 1 &&
                map[x + 1][y] != 1 &&
                map[x + 1][y + 1] != 1) {
                return true;
            }
        }

        // 현재 파이프가 세로 방향일 때
        else if (dir == 2) {

            // 세로 -> 세로 (아래로 한 칸)
            // (x+1, y) 칸만 확인
            if (next == 2 && map[x + 1][y] != 1) {
                return true;
            }

            // 세로 -> 대각선
            // 오른쪽, 아래, 오른쪽 아래 총 3칸 확인
            if (next == 3 &&
                map[x][y + 1] != 1 &&
                map[x + 1][y] != 1 &&
                map[x + 1][y + 1] != 1) {
                return true;
            }
        }

        // 현재 파이프가 대각선 방향일 때
        else if (dir == 3) {

            // 대각선 -> 가로
            // 오른쪽 칸만 비어 있으면 됨
            if (next == 1 && map[x][y + 1] != 1) {
                return true;
            }

            // 대각선 -> 세로
            // 아래 칸만 비어 있으면 됨
            if (next == 2 && map[x + 1][y] != 1) {
                return true;
            }

            // 대각선 -> 대각선
            // 오른쪽, 아래, 오른쪽 아래 모두 확인
            if (next == 3 &&
                map[x][y + 1] != 1 &&
                map[x + 1][y] != 1 &&
                map[x + 1][y + 1] != 1) {
                return true;
            }
        }

        // 이동 불가능한 경우
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        // 경계 처리를 쉽게 하기 위해 n+2 크기로 생성
        map = new int[n + 2][n + 2];

        StringTokenizer st;

        // 지도 입력
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = st.nextToken().charAt(0) - '0';
            }
        }

        // 외곽을 전부 벽(1)으로 처리
        // 범위 체크를 하지 않아도 되도록 하기 위함
        for (int i = 0; i <= n + 1; i++) {
            map[i][0] = 1;
            map[i][n + 1] = 1;
            map[0][i] = 1;
            map[n + 1][i] = 1;
        }

        /**
         * dp[dir][i][j]
         * (i, j)에 파이프 끝이 위치하고
         * dir 방향으로 놓여 있는 경우의 수
         *
         * dir
         * 0 : 가로
         * 1 : 세로
         * 2 : 대각선
         */
        int[][][] dp = new int[3][n + 2][n + 2];

        // 시작 상태
        // (1,1)~(1,2) 가로 방향이므로
        dp[0][1][2] = 1;

        // 모든 칸을 순회하면서 DP 누적
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {

                // 현재 가로 방향으로 도착한 경우
                if (dp[0][i][j] > 0) {

                    // 가로 -> 가로
                    if (check(i, j, 1, 1))
                        dp[0][i][j + 1] += dp[0][i][j];

                    // 가로 -> 대각선
                    if (check(i, j, 1, 3))
                        dp[2][i + 1][j + 1] += dp[0][i][j];
                }

                // 현재 세로 방향으로 도착한 경우
                if (dp[1][i][j] > 0) {

                    // 세로 -> 세로
                    if (check(i, j, 2, 2))
                        dp[1][i + 1][j] += dp[1][i][j];

                    // 세로 -> 대각선
                    if (check(i, j, 2, 3))
                        dp[2][i + 1][j + 1] += dp[1][i][j];
                }

                // 현재 대각선 방향으로 도착한 경우
                if (dp[2][i][j] > 0) {

                    // 대각선 -> 가로
                    if (check(i, j, 3, 1))
                        dp[0][i][j + 1] += dp[2][i][j];

                    // 대각선 -> 세로
                    if (check(i, j, 3, 2))
                        dp[1][i + 1][j] += dp[2][i][j];

                    // 대각선 -> 대각선
                    if (check(i, j, 3, 3))
                        dp[2][i + 1][j + 1] += dp[2][i][j];
                }
            }
        }

        // (n, n)에 도달하는 모든 방향의 경우의 수 합
        System.out.println(
            dp[0][n][n] + dp[1][n][n] + dp[2][n][n]
        );
    }
}

함께 읽으면 좋은 글

코딩 테스트2026-04-02

5430번 - AC

함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…

코딩 테스트2026-04-02

1966번 - 프린터 큐

여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…

코딩 테스트2026-03-29

1158 - 요세푸스 문제

1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.

코딩 테스트2026-03-29

2164번 - 카드2

1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.

← 서재 목록으로 돌아가기