[그래프 탐색] 17070번 - 파이프 옮기기1

[백준] 17070번 - 파이프 옮기기1

📝 나의 풀이

📌 가로일 때 이동 가능한 경우

📌 세로일 때 이동 가능한 경우

📌 대각선일 때 이동 가능한 경우

각 방향대로 이동할 때 무조건 빈칸이어야 하는 조건도 잘 성립하도록 주의해야 한다.

가능한 모든 방향을 탐색하고, 파이프의 한쪽 끝이 (N-1, N-1)에 도착하면
경우의 수를 세는 count 변수를 증가시켜주면 된다.

👩🏻‍💻 최종 코드

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

public class Main {

	static int N, count;
	static int[][] map;
	static boolean[][] visited;
	
	private static int getDirection(int diffX, int diffY) {
		if(diffX == 0 && diffY == 1) return 0; //가로 방향
		else if(diffX == 1 && diffY == 0) return 1; //세로 방향
		else if(diffX == 1 && diffY == 1) return 2; //대각선 방향
		
		return -1;
	}
	
	private static boolean isValid(int x, int y) {
		return x >= 0 && y >= 0 && x < N && y < N;
	}
	
	private static void moveHorizontal(int x1, int y1, int x2, int y2) {
		x1 = x2;
		y1 = y2;
		x2 = x2 + 0;
		y2 = y2 + 1;
			
		if(isValid(x2, y2) && !visited[x2][y2] && map[x2][y2] == 0) {
			visited[x2][y2] = true;
			dfs(x1, y1, x2, y2);
			visited[x2][y2] = false;
		}	
		
	}
	
	private static void moveVertical(int x1, int y1, int x2, int y2) {
		x1 = x2;
		y1 = y2;
		x2 = x2 + 1;
		y2 = y2 + 0;
			
		if(isValid(x2, y2) && !visited[x2][y2] && map[x2][y2] == 0) {
			visited[x2][y2] = true;
			dfs(x1, y1, x2, y2);
			visited[x2][y2] = false;
		}	
		
	}
	
	private static void moveDiagonal(int x1, int y1, int x2, int y2) {
		x1 = x2;
		y1 = y2;
		x2 = x2 + 1;
		y2 = y2 + 1;
			
		if(isValid(x2, y2) && !visited[x2][y2] && map[x2][y2] == 0 && map[x2-1][y2] == 0 && map[x2][y2-1] == 0) {
			visited[x2][y2] = true;
			dfs(x1, y1, x2, y2);
			visited[x2][y2] = false;
		}	
		
	}
	
	private static void dfs(int x1, int y1, int x2, int y2) {
		if(x2 == N -1 && y2 == N -1) count++;
		
		int flag = getDirection(x2 - x1, y2 - y1);
		
		switch(flag) {
		case 0:
			moveHorizontal(x1, y1, x2, y2);
			moveDiagonal(x1, y1, x2, y2);
			break;
		case 1:
			moveVertical(x1, y1, x2, y2);
			moveDiagonal(x1, y1, x2, y2);
			break;
		case 2:
			moveHorizontal(x1, y1, x2, y2);
			moveVertical(x1, y1, x2, y2);
			moveDiagonal(x1, y1, x2, y2);
			break;
		}
	}
	
	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];
		visited = new boolean[N][N];
		
		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, 0, 0, 1);
		
		System.out.println(count);
	}

}

---

Review

나는 나한테 가장 편한 방법인 DFS로 구현했는데
검색해보니 BFS, DP를 활용해서 푼 사람들도 많았다.
나중에 다른 방법으로도 풀어보고, 더 효율적인 코드를 구현해봐야겠다.