[BOJ] 17070. 移動パイプ1

質問する

に答える

次の方向が対角線の場合は壁があるか確認する.

ここで青く塗った部分に壁があると移動できません!!

JAvaコード

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Main {
	static int N;
	static int [][] map; // 격자판 정보 저장
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new int[N][N];
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
        
        	// (N-1, N-2)이 벽인 경우
		if (map[N-1][N-1] == 1) {
			System.out.println(0);
			return;
		}
		
		System.out.println(BFS());
	}
	
	private static int BFS() {
		int count = 0;
		Queue<Cord> q = new LinkedList<>();
		q.add(new Cord(0, 1, -1)); // start 가로(-1)로 시작 
		
		Cord cur; // 현재 파이프의 끝 좌표
		int d; // -1 가로 0 대각 1 세로 
		int nr, nc; // 파이프의 끝이 이동될 좌표
		
		while(!q.isEmpty()) {
			cur = q.poll();
			d = cur.dir; // 현재 파이프가 놓여진 방향
			
			// 대각선으로 나아감 
			nr = cur.r+1; nc = cur.c+1;
			// 격자판 밖인지 + 벽이 없는지 확인
			if (nr<N && nc<N && map[cur.r][nc]==0 && map[nr][cur.c]==0 && map[nr][nc]==0) {
				if (nr == N-1 && nc == N-1) {
					count++; // 도착
				} else if (nr<N && nc<N) {
					q.add(new Cord(nr, nc, 0)); // 다음) 대각선 방향
				}
			}

			// 세로로 나아감
			if (d >= 0) {
				nr = cur.r+1; nc=cur.c;
				if (nr == N-1 && nc == N-1) {
					count++; // 도착
				} else if (nr<N && nc<N && map[nr][nc]!=1) { // 벽이 아닐 때
					q.add(new Cord(nr, nc, 1)); // 다음) 세로 방향
				}
			}
			
			// 가로로 나아감 
			if (d <= 0) {
				nr = cur.r; nc=cur.c+1;
				if (nr == N-1 && nc == N-1) {
					count++; // 도착
				} else if (nr<N && nc<N && map[nr][nc]!=1) { // 벽이 아닐 때 
					q.add(new Cord(nr, nc, -1)); // 다음) 가로 방향
				}
			}
			
		}
		
		return count;
	}
	
	static class Cord {
		int r;
		int c;
		int dir;
		Cord(int r, int c, int dir) {
			this.r = r;
			this.c = c;
			this.dir = dir;
		}
	}
}

まちがった理由

改善方向

/**
 * @param next 다음좌표, 방향(파라미터로 넘길)
 * @return 1 도착 0 못도착
 */
int nextCord(Cord next, Queue<Cord> q);