[BOJ] 17070. 파이프 옮기기 1

문제

파이프 옮기기 1
격자판의 첫 번째 칸(0,0)에 가로로 파이프가 놓여있다.
이 파이프를 맨 마지막 위치 (N-1, N-1)로 옮기는 경우의 수를 출력해라.

이때, 파이프는 밀면서 이동시킨다. 밀 수 있는 방향은 놓여진 경우에 따라 다르고, 벽이 있으면 이동하지 못한다.

풀이

1. 파이프를 미는 방향은 오른쪽, 아래, 오른쪽 아래 3가지인데, 현재 파이프가 놓여져 있는 방향에 따라 다르다.

• 파이프의 끝(가장 오른쪽 아래)을 현재좌표라 생각하고, 현재 놓여져 있는 방향도 저장했다.
  Cord 클래스
  방향 : -1 가로, 0 대각선, 1 세로
• BFS로 나아갈 수 있는 좌표를 탐색했다. [대각선/세로/가로] 3가지 가능!
  • 다음 방향이 대각선인 경우 벽이 있는지 확인해줘야한다.
    
    여기서 하늘색으로 칠해진 부분에 벽이 있으면 이동불가!!
  • (N-1, N-1) 에 도착했다면 count++
  • 아직 도착못했고, 격자판 내부의 영역이라면 queue에 추가. 이때 현재 이동방향도 담아준다.

2. (N-1, N-2)이 벽인 경우도 고려해줘야한다.

• 0 출력하고 끝 ~

자바코드

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] != 1 로 했다 ㅎ... map[nr][nc]인데..ㅎ
• 도착지점이 벽인 경우를 고려하지 못했음
  
  (+)기타이유
• C++로 제출해서.. ㅜㅜ
• Solution 클래스로 제출해서..ㅜㅜ

개선방향

BFS() 내부를 보면 대각선, 가로, 세로 로 나뉘어져 있지만 코드가 거의 똑같다! 함수로 빼면 좋을 것 같다.

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