[BOJ]17070パイプ移動1(Java)

移动管路1

質問する

アルゴリズム#アルゴリズム#

DFS

に答える

アルゴリズム学習では,学習者の解題方式がよいので,この方法で解題する.

まずパイプタイプによってすべての行ける方向に移動し、

配管の移動方向に壁がある場合は、これ以上行われません.

パイプが特定の方向(右、右、下)に移動できる場合、その方向に従って対応するインデックスに移動します.
この場合,問題で与えられた図とは異なり,パイプは,,|の3つの方向のうちの1つの方向を有し,1つの格子しか占めていないと考えれば便利である.

コード#コード#

'''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);
		}
	}
	
}

}
'''