[백준]boj 17070 파이프 옮기기1

접근 방법

1. 갈 수 있는 방향에 대한 인덱스를 2차원 배열에 저장하였습니다. 방향에 대한 이동은 dir 이차원 배열을 이용하여 오른쪽 이동, 아래로 이동, 대각선 이동을 구현하였습니다.

2. 재귀를 진행하면서 현재 방향으로 갈 수 있는 경우에 대해 모든 탐색을 진행하였습니다. 이를 위해 현재 방향에 대해 매개변수로 넘겨줍니다.

 

 

구현하며 어려웠던 점

1. 문제 조건을 하나 빼먹었는데, 빈칸이어야 하는 곳에 대한 확인이 없었습니다.

조건1

 

추가 접근 방안

1. dp로도 이 문제를 접근할 수 있습니다.

 

public class Main_17070 {
	
	private static int N;
	private static int[][] maps;
	private static boolean[][] visited;
	private static int result;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		maps = new int[N][N];
		visited = new boolean[N][N];
		
		StringTokenizer st = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				maps[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		visited[0][1] = true;//시작 위치 
		solve(0, 1, 0);
		
		System.out.println(result);
	}
	

	
	private static int[][] dir = {{0, 1}, {1, 0}, {1, 1}};//오른쪽, 아래, 대각선
	
	//갈 수 있는 방향에 대한 인덱스 저장
	private static int[][] types = {
			{0, 2},//가로
			{1, 2},//세로
			{0, 1, 2}//대각선
	};
	
	
	/**
	 * @param count
	 * @param row
	 * @param col
	 * @param nowType 0=가로, 1=세로, 2=대각선
	 */
	private static void solve(int row, int col, int nowType) {
		if(row == N - 1 && col == N - 1) {
			result++;
			return;
		}
		
		
		
		int nextX = 0;
		int nextY = 0;
	
		for (int i = 0; i < types[nowType].length; i++) {
			nextX = row + dir[types[nowType][i]][0];
			nextY = col + dir[types[nowType][i]][1];
			
			if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
			if(visited[nextX][nextY]) continue;
		
			//빈칸 조건 확인
			if(maps[nextX][nextY] == 1) {
				continue;
			}
			if(types[nowType][i] == 2) {//대각선인 경우
				if(maps[nextX-1][nextY] == 1 || maps[nextX][nextY-1] == 1) {
					continue;
				}
			}
			visited[nextX][nextY] = true;
			solve(nextX, nextY, types[nowType][i]);
			visited[nextX][nextY] = false;
		}
	}
	
	
	
}