[BOJ] 17070. 移動パイプ1

質問する

移動パイプ1
格子板の最初の格子(0,0)に横にパイプが置いてあります.
このパイプを最後の位置(N-1,N-1)に移動すると、数量を出力します.
このとき、チューブは押しながら移動します.押す方向は置く場合によって異なり、壁があると移動できません.

に答える

パイプを押す方向は右、下、右下の3種類あり、現在のパイプが置かれている方向によって異なります.

パイプの先端(右下隅)を現在の座標とし、現在の配置方向を保存します.Cord 클래스方向:-1横、0対角線、1縦

BFSに通じる座標を探索した.[対角線/縦/横]3種類可能!

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

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

(N-1,N-1)count++

到着していないが、グリッドボード内部の領域であればキューに追加する.このとき、現在移動している方向も含まれています.

(N-1,N-2)壁の場合も含めて.

0出力して終了~

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

まちがった理由

壁の部分コードを確認map[nc][nr] != 1map[nr][nc]

壁に立つことを考慮していない
(+)その他の原因

C++で提出…うううう

ソリューションクラスに提出…うううう

改善方向

BFS()内部から見ると、対角線、横線、縦線に分かれていますが、コードはほぼ同じ!関数に減らすといいはずです.

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