[백준] 17070번. 파이프 옮기기1 (JAVA)

https://www.acmicpc.net/problem/17070

---

문제

---

풀이

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

public class Main {

    static int n, cnt;
    static int[][] map;

    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][n];
        cnt = 0;
        StringTokenizer st;
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 1, 0);

        System.out.println(cnt);
    }


    
    static void dfs(int x, int y, int state) {// State -> 0: 가로 , 1: 세로, 2: 대각선
        if (x == n - 1 && y == n - 1) {
            cnt++;
            return;
        }

        if(state == 0){
            if(y+1 < n && map[x][y+1] == 0){
                dfs(x, y + 1, 0);
            }
        }else if(state == 1){
            if(x+1 < n && map[x+1][y] == 0){
                dfs(x+1, y, 1);
            }
        }else if(state == 2){
            if(y+1 < n && map[x][y+1] == 0){
                dfs(x, y + 1, 0);
            }
            if(x+1 < n && map[x+1][y] == 0){
                dfs(x+1, y , 1);
            }
        }

        if (x + 1 < n && y + 1 < n && map[x][y + 1] == 0 && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0) {
            dfs(x + 1, y + 1, 2);
        }

    }

}

 

방향을 직접 나눠가며 dfs를 통해 해결하는 방법이다.

dfs문제 자체로는 어렵지 않았지만 가장 마지막의 대각선 처리가 주요하다. 현재 방향에 따라 가로, 세로, 대각선의 이후 가로 세로 움직임에 대해서는 각각 검사하지만(모두 다르므로), 대각선 방향은 어떤 상태이든 진행을 검사해야 하니 따로 빼놓고 진행한다.

물론 각각의 방향 안에 if문을 따로 넣어도 되겠지만 그렇게 하는 것보다 마지막으로 빼는 것이 더욱 깔끔해보여서 그렇게 했다.

 

또한, 끝쪽의 위치한 중요하므로  x,y의 위치를 어렵게 생각하기보다는 끝쪽만 잡았다.

 

마지막으로 백트래킹을 해야되나 생각했는데 생각해 보니까 방문했다고 뭐가 바뀌는 것도 아니고, 최종적으로 카운트에만 안 들어가면 되는 것이기 때문에 하지 않아도 된다고 결론을 내려 진행하지 않았다!!

 

매번 dfs, bfs 문제를 풀 때마다 느끼는 것이지만 갈피를 잡아도 정확히 잡아두지 않고 시작하면 고생을 하게 되는 것 같으니 더욱 감을 익히고 천천하고 정확하게 사용하는 연습을 해야 될 것 같다.