[BOJ] 17070 파이프 옮기기1 (Java)

파이프 옮기기 1

문제

알고리즘

DFS

풀이

알고리즘 스터디 중, 스터디원이 푼 방식이 되게 괜찮은 방식이어서 이 방법대로 풀어보았다..

1. 먼저 파이프 타입별로 갈 수 있는 모든 방향으로 이동시켜본다
2. 만약 파이프가 있는 이동하려는 방향에 벽이 있다면, 그 경우는 더 이상 진행하지 않는다.
3. 파이프가 특정 방향(우, 우하, 하)으로 이동할 수 있는 경우에, 그 방향을 가지고 해당 인덱스로 이동한다.
   이 때, 문제에서 제시된 그림과 다르게 파이프는 -, \, | 이 세 가지 방향 중 하나를 가지고, 한 칸을 차지한다고 생각하면 편하다.
   

코드

'''java
import java.util.;
import java.io.;

public class Main {

static int N, answer;
static int[][] map;
static int[] dr = {0, 1, 1};	// 우 우하 하
static int[] dc = {1, 1, 0};	// 우 우하 하 
static int[][] possibleDir = {{0,1}, {0,1,2}, {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][N];
	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());	// 0은 갈 수 있는 공간, 1은 벽 
		}
	}
	
	answer = 0;
	dfs(0, 1, 0);
	System.out.println(answer);
}
private static void dfs(int r, int c, int d) {
	if(r==N-1 && c==N-1) {
		answer++;
		return;
	}
	
	int[] dirs = possibleDir[d];
	for(int dir : dirs) {
		int nr = r + dr[dir];
		int nc = c + dc[dir];
		
		boolean flag = true;
		if(dir==1) {
			// 우하로 이동할 경우, 우/우하/하 방향이 모두 비어있어야됨 
			for(int i=0; i<3; i++) {
				int rr = r + dr[i];
				int cc = c + dc[i];
				if(rr<0||rr>=N || cc<0||cc>=N || map[rr][cc]==1) {
					flag = false;
					break;
				}
			}
		} else {
			if(nr<0||nr>=N || nc<0||nc>=N || map[nr][nc]==1) {
				flag = false;
			}
			
		}
		
		if(flag) {
			dfs(nr, nc, dir);
		}
	}
	
}

}

'''