이것저것 개발 블로그

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

문제

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BJ_17070_파이프옮기기1 {

	static int n, ans;
	static int[][] map;
	static int[] direction = {0, 1, 2};//순서대로 가로, 세로, 대각선
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		map = new int[n+1][n+1];
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}	
		} //map
		
		
		int dir = 0;
		int x=1;
		int y=2;
		route(x, y, dir);
		System.out.println(ans);
		
	}//main
	
	private static void route(int x, int y, int dir) {
		if(x == n && y==n)
			ans++;
		
		switch(dir) {
		case 0:
			// 동쪽
			if(y+1 <= n && map[x][y+1] == 0) {
				route(x, y+1, 0);
			}
			// 동남쪽
			 if(x+1 <=n && y+1<=n && map[x+1][y]==0 && map[x+1][y+1]==0 && map[x][y+1]==0) {
				 route(x+1, y+1, 2);
			 }
			break;
			
		case 1:
			//남쪽
			if(x+1 <= n && map[x+1][y] == 0) {
				route(x+1, y, 1);
			}
			//동남쪽
			if(x+1 <=n && y+1<=n && map[x+1][y]==0 && map[x+1][y+1]==0 && map[x][y+1]==0) {
				 route(x+1, y+1, 2);
			 }
			break;
		case 2:
			//동쪽
			if(y+1 <= n && map[x][y+1] == 0) {
				route(x, y+1, 0);
			}
			//남쪽
			if(x+1 <= n && map[x+1][y] == 0) {
				route(x+1, y, 1);
			}
			//동남쪽
			 if(x+1 <=n && y+1<=n && map[x+1][y]==0 && map[x+1][y+1]==0 && map[x][y+1]==0) {
				 route(x+1, y+1, 2);
			 }
			break;
		}
		
		
		
	}//route
	
}

각 방향대로 보면 된다.

0: 가로 / 1: 세로 / 2: 대각선

각 방향별로 갈 수 있는 방향이 정해져있다.

예를 들어, 가로는 동쪽과 동남쪽이 있음!!

해당하는 경우마다 범위를 계산하고, map이 0인지 아닌지를 판단한다.(문제 조건)

그리고 DFS로 계속 이동하면 됨!! 

DP로 하는 방법도 있는데, 3차원 배열을 선언해서,

각 가로, 세로, 대각선에 해당하는 것을 범위를 확인하면서 진행하고, 계속 더해나가주면 된다.