백준 17070번 : 파이프 옮기기 1 java

이 문제는 파이프가 어디로 이동할 수 있는지를 확인해주면서 벽에 닿을 때만 제외해주면 되는 문제입니다.

이 문제를 풀 때 파이프가 현재 가로 방향에 있는지, 세로 방향인지, 대각선 방향인지에 따라서 경우를 나누어주면 됩니다.

파이프의 끝 점을 기준으로 문제를 푸는 과정을 그림으로 보여드리겠습니다.

위의 그림은 N이 4일 때를 나타냈습니다. 이제 이 파이프가 이동할 수 있는 경로를 찾아보겠습니다.

우선 오른쪽으로 파이프를 이동시키겠습니다.

이렇게 파이프가 위치하면 파이프가 가로 방향으로 위치해 있기 때문에 오른쪽과 오른쪽 대각선 아래 방향이 가능합니다.

이 두 방향으로 파이프를 이동시켜 보겠습니다.

파이프를 가로로 이동시켰을 때는 (4, 4)로 갈 수 없습니다.

하지만 대각선으로 파이프를 이동시켰을 때 세로 방향으로 2번 파이프를 이동시키면 (4, 4)에 도달할 수 있습니다.

다음과 같은 경로로 (4, 4)에 도달할 수 있습니다.

이러한 규칙을 통해서 파이프를 이동시킬 수 있습니다.

이제 코드를 보면서 추가로 설명드리겠습니다.

---

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

public class Main {
    static int N;
    static int[][] map;
    static int count = 0;
    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+1][N+1];

        for(int i = 1; i<=N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j = 1; j<=N; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }

        dfs(1, 2, 0);

        System.out.println(count);
    }

    //dir이 0이면 가로 1이면 세로 2면 대각선
    static void dfs(int row, int col, int dir){
        if(row>N || col>N || map[row][col] == 1)
            return;
        if(dir == 2){
            if(map[row][col-1] == 1 || map[row-1][col] == 1)
                return;
        }
        if(row == N && col == N){
            count++;
            return;
        }

        if(dir == 0){
            dfs(row, col+1, 0);
            dfs(row+1, col+1, 2);
        }
        else if(dir == 1){
            dfs(row+1, col, 1);
            dfs(row+1, col+1, 2);
        }
        else{
            dfs(row+1, col+1, 2);
            dfs(row, col+1, 0);
            dfs(row+1, col, 1);
        }
    }
}

저는 이 문제를 dfs로 풀었습니다. dfs로 (N, N)지점에 파이프의 끝 점이 가게 된다면 count++를 해준 다음 return했습니다.

 

또한 대각선으로 움직일 경우 아래의 그림과 같이 파이프의 끝 점의 위와 왼쪽도 비어있어야 합니다.

따라서 저는 아래와 같은 조건을 dfs 함수가 시작할 때 두어서 대각선으로 이동했는데 
map[row][col-1](파이프의 끝 점의 왼쪽) 와 map[row-1][col](파이프의 끝 점의 위)에 벽이 있으면 이 방향으로는 파이프를 이동시킬 수 없으므로 다른 경로를 탐색하게 하였습니다. 

if(dir == 2){
    if(map[row][col-1] == 1 || map[row-1][col] == 1)
        return;
}