[17070] 파이프 옮기기 1 in Java

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

17070번: 파이프 옮기기 1

---

문제 요약

- 1<=r,c<=n
- 빈칸 : 0, 벽 : 1
- 파이프 이동 방향 : 우, 우하, 하
- 파이프 회전 : 45도만 가능
- 파이프 이동 방법 : 가로일 경우 : →, ↘
                             세로일 경우 : ↘, ↓ 
                                     대각선일 경우 : →, ↘, ↓
- 꼭 비어있어야 하는 칸: 가로일 경우 : 1칸
                                  세로일 경우 : 1칸
                                     대각선일 경우 : 3칸
- 초기 파이프 위치 (1,1) , (1,2) , (참고로 해당 칸은 항상 빈칸이다)
- 초기 파이프 방향 : 가로

파이프의 한쪽 끝을 (N,N)으로 이동시키는 방법의 개수는?
만약 해당 칸으로 이동이 불가하면 0을 출력한다.

 

---

접근 방식

 

- dfs 기법 사용

: 이동이 가능하면 해당 위치를 기준으로 재귀함수 호출

 

 

 

---

시행 착오

- cnt를 x가 n-1, y가 n-1에 도착했을때만 +1 해줘야하는데, 

can_go(nx,ny)가 충족할때마다 cnt를 해줘서 원하는 값이 나오지 않았음.

 

- 가로일때 갈 수 있는 방향이 →, ↘이다.

그래서 방향 인덱스가 0, 2여야하는데

for문을 사용할 때 증감을 +2가 아닌 +1로 해서 원하는 값이 안 나옴..

 

- 대각선일 땐 3칸을 can_go()함수를 돌려봐야 한다.

그런데 이 생각을 못함 ㅎ..ㅎ

 

 

 

 

 

 

package day_0810;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class study17070 {
    static int n;
    static int[][] array;
    static int cnt;
    
    public static boolean can_go(int x,int y) { // x,y 위치로 이동이 가능한지 판별하는 함수
        if (x>=0 && x<n && y>=0 && y<n && array[x][y]==0) return true; // 빈칸이고 이동이 가능하면 true 반환
        return false;
    }
    
    public static void move(int x,int y, int dir) {
        if (x==n-1 && y==n-1) { // 목적지에 도착했을 경우
            cnt++; // 이동횟수 +1 증가
            return;
        }
        
        int[] dxs= {0,1,1}; // →,↓,↘ (가로, 세로, 대각선 순)
        int[] dys= {1,0,1}; // →,↓,↘
        
        if (dir==0) { // 현재 방향이 가로일 경우 : →, ↘
            for (int d = 0; d < 3; d+=2) { 
                int nx=x+dxs[d];
                int ny=y+dys[d];
                if (can_go(nx,ny)) {
                    if (d==0) move(nx,ny,d); // 가로 방향으로 이동하고자 할 때
                    else { // 대각선 방향으로 이동하고자 할 때
                        if (can_go(nx,ny) && can_go(x+dxs[0],y+dys[0]) && can_go(x+dxs[1],y+dys[1])) {
                            move(nx,ny,d);
                        }
                    }
                }
            }
        }else if(dir==1) { // 현재 방향이 세로일 경우 : ↘, ↓ 
            for (int d = 1; d < 3; d++) {
                int nx=x+dxs[d];
                int ny=y+dys[d];
                if (can_go(nx,ny)) {
                    if (d==1) move(nx,ny,d); // 세로 방향으로 이동하고자 할 때
                    else { // 대각선 방향으로 이동하고자 할 때
                        if (can_go(nx,ny) && can_go(x+dxs[0],y+dys[0]) && can_go(x+dxs[1],y+dys[1])) {
                            move(nx,ny,2);
                        }
                    }
                }
                
            }
        }else { // 현재 방향이 대각선일 경우 : →, ↘, ↓
            for (int d = 0; d < 3; d++) {
                int nx=x+dxs[d];
                int ny=y+dys[d];
                if (can_go(nx,ny)) {
                    if (d<=1) move(nx,ny,d); // 가로, 세로 방향으로 이동하고자 할 때
                    else { // 대각선 방향으로 이동하고자 할 때
                        if (can_go(nx,ny) && can_go(x+dxs[0],y+dys[0]) && can_go(x+dxs[1],y+dys[1])) {
                            move(nx,ny,d);
                        }
                    }
                }
            }
        }
}
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n= Integer.parseInt(br.readLine()); // 격자 크기
        array=new int[n][n];
        
        for (int i = 0; i < n; i++) {            
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                array[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        int dir = 0; // 초기 방향 : 가로
        move(0,1,dir); // 파이프 앞쪽 위치 -> 이게 n-1, n-1이 되어야함
        System.out.println(cnt);
        
    }
}