[BOJ/Java] 17070. 파이프 옮기기 1

[BOJ/Java] 17070. 파이프 옮기기 1

17070번: 파이프 옮기기 1

---

문제 해석

이 문제는 주어진 격자 안에서 파이프를 조작하여 시작 위치에서 목표 위치까지 이동하는 경로의 수를 찾는 문제다. 파이프는 가로, 세로, 대각선의 3가지 상태로 움직일 수 있으며, 격자의 범위와 벽(값 1)에 의해 움직임이 제한된다. 파이프는 격자의 한 쪽 끝에서 다른 쪽 끝으로만 연장될 수 있으며, 목적지에 도달할 때마다 가능한 경로의 수를 세어야 한다.

풀이 과정

제출된 코드는 깊이 우선 탐색(DFS)를 사용하여 모든 가능한 경로를 탐색한다. 코드에서는 각 파이프 상태에 따른 이동 가능 방향을 direction 배열로 정의하고, 대각선 이동을 시도할 때 추가 검증을 위한 check 배열을 사용한다. 각 상태에서 가능한 이동을 시도하고, 조건에 맞는 경우 재귀적으로 다음 상태를 탐색한다. 목적지에 도달할 때마다 ans 변수를 증가시켜 가능한 경로의 수를 기록한다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No17070;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    // 각 파이프 상태(가로, 세로, 대각선)에 따른 이동 가능 방향 정의
    private final static int[][][] direction = {
        { { 0, 1 }, { 1, 1 } }, // 가로 상태에서 이동 가능 방향
        { { 1, 0 }, { 1, 1 } }, // 세로 상태에서 이동 가능 방향
        { { 0, 1 }, { 1, 0 }, { 1, 1 } } // 대각선 상태에서 이동 가능 방향
    };

    // 대각선 이동시 검증 필요 영역
    private final static int[][] check = { { 0, 1 }, { 1, 0 }, { 1, 1 } };

    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().io();
    }

    private int n; // 격자 크기
    private int[][] map; // 격자 정보
    private int ans = 0; // 가능한 경로의 수

    private void io() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine()); // 격자 크기 입력
        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());
            }
        }

        dfs(0, 1, 0); // DFS 시작 (초기 상태: 가로)
        
        sb.append(ans); // 결과 출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void dfs(int x, int y, int d) { // DFS 탐색 함수
        if (x == n-1 && y == n-1) {
            ans++; // 목적지에 도달
            return;
        }

        for (int dr = 0; dr < direction[d].length; dr++) {
            int nx = x + direction[d][dr][0];
            int ny = y + direction[d][dr][1];
            if (nx >= n || ny >= n || map[nx][ny] == 1) continue; // 범위를 벗어나거나 벽인 경우

            if (dr == 2) { // 대각선 이동 시 추가 검증
                boolean flag = true;
                for (int c = 0; c < check.length; c++) {
                    int cx = x + check[c][0];
                    int cy = y + check[c][1];
                    if (map[cx][cy] == 1) {
                        flag = false;
                        break;
                    }
                }
                if (flag) dfs(nx, ny, 2);
            } else { // 가로 또는 세로 이동
                dfs(nx, ny, dr);
            }
        }
    }
}

시간 복잡도 분석

이 코드는 각 상태에 대해 가능한 모든 이동을 시도하며, 최악의 경우 𝑂(3^(𝑛^2))의 시간 복잡도를 가질 수 있다. 그러나 실제로는 많은 이동이 벽이나 격자의 범위 때문에 제한되므로, 평균적인 시간 복잡도는 이보다 낮을 것이다.

느낀점

이 문제를 통해 다차원 배열을 이용한 상태 관리와 깊이 우선 탐색을 통한 복잡한 경로 탐색 문제를 해결하는 방법을 더 잘 이해할 수 있었다. 이러한 탐색 기법은 많은 알고리즘 문제에서 유용하게 사용될 수 있다.