Problem Info

Name : 파이프 옮기기 1

No : 17070

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

Start Time : 15:06

End Time : 15:51

Result(Pass / Failed) : Pass

Strategy

Algorithm: DFS

Calculating time complexity: O(n^2) 예상

Code Answer

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

public class Main
{
    static int n;
    static int[][] map = new int[20][20];
    static int[] dy = {0, 1, 1};
    static int[] dx = {1, 0, 1};
    static int count = 0;
    
    static void dfs(int y, int x, int dir){
        
        if(y == n-1 && x == n-1 ){ // (n-1, n-1) 방문했다는 것은 도착했다는 것.
            count++;
            return;
        }
        
        for(int d = 0; d < 3 ; d++){
            int ny = y + dy[d];
            int nx = x + dx[d];
            
            if( ny < 0 || nx < 0 || ny >= n || nx >= n ) continue; // 범위 밖 불가
            if( map[ny][nx] == 1 ) continue;   // 벽 이동 불가
            if( dir == 0 && d == 1 ) continue; // 가로 -> 세로 이동 불가
            if( dir == 1 && d == 0 ) continue; // 세로 -> 가로 이동 불가
            // 대각선일 때 회전할 공간이 벽이면 긁으므로 불가
            if( d == 2 && ( map[ny-1][nx] == 1 || map[ny][nx - 1] == 1 )) continue; 
            
            dfs(ny, nx, d);
        }
    }
    
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st; 
	    
	    n = Integer.parseInt(br.readLine());
	   
	    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); // 1,2 부터 가로방향으로 시작
	    
		System.out.println(count);
	}
}

If you failed, Why?