백준_통나무 옮기기_1938[Java]

문제

https://www.acmicpc.net/problem/1938

1938번: 통나무 옮기기

 

풀이

앞서 풀었던 로봇 문제와 풀이 방법이 매우 유사하지만 조건이 조금 까다롭다.

BFS로 풀이하되 회전이 이동과 같은 타이밍에 할 수 있도록 조건을 준다.

 

* 주의할 점

통나무가 목표지점에 절대 도달하지 못하는 경우가 있다. 이때 0을 출력해야 한다.

 

- TEST CASE

input : 

4
BBB1
1111
1111
1EEE
output : 0

 

그 외 샘플테스트는 다른 분들이 올려주신것을 참고해보자 ! 링크

코드

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

public class Main {
	static int N;
	static char[][] map;
	static boolean[][][] visit;

	static final int VERTICAL = 0;
	static final int HORIZON = 1;

	static Logs start, end;

	static class Logs {
		int x;
		int y;
		int dir;
		int cnt;

		Logs(int x, int y, int dir, int cnt) {
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.cnt = cnt;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		sc.nextLine();

		map = new char[50][50];
		visit = new boolean[50][50][2];

		start = new Logs(-1, -1, -1, 0);
		end = new Logs(-1, -1, -1, 0);
		int sCnt = 1;
		int eCnt = 1;

		for (int i = 0; i < N; i++) {
			String s = sc.nextLine();

			for (int j = 0; j < N; j++) {
				map[i][j] = s.charAt(j);
				if (map[i][j] == 'B') {
					if (sCnt == 1) {
						start.x = j;
						start.y = i;
						sCnt++;
					} else if (sCnt == 2) {
						if (start.x == j)
							start.dir = VERTICAL;
						else
							start.dir = HORIZON;
						start.x = j;
						start.y = i;
						sCnt++;
					}
				}

				if (map[i][j] == 'E') {
					if (eCnt == 1) {
						end.x = j;
						end.y = i;
						eCnt++;
					} else if (eCnt == 2) {
						if (end.x == j)
							end.dir = VERTICAL;
						else
							end.dir = HORIZON;
						end.x = j;
						end.y = i;
						eCnt++;
					}
				}
			}
		}

		//System.out.println(start.x + " , " + start.y + " , " + start.dir);
		//System.out.println(end.x + " , " + end.y + " , " + end.dir);

		dfs();
		visit[start.y][start.x][start.dir] = true;

		sc.close();
	}

	static int[] dx = { 0, 0, -1, 1, 0 };
	static int[] dy = { -1, 1, 0, 0, 0 };

	private static void dfs() {
		Queue<Logs> q = new LinkedList<Logs>();
		q.add(new Logs(start.x, start.y, start.dir, 0));

		while (!q.isEmpty()) {
			Logs curLog = q.poll();
			int curX = curLog.x;
			int curY = curLog.y;
			int curDir = curLog.dir;
			int cnt = curLog.cnt;

			// 기저사례 추가해야한다.
			if(curX == end.x && curY == end.y && curDir == end.dir) {
				System.out.println(cnt);
				return;
			}

			for (int i = 1; i <= 5; i++) {
				int nextX = curX + dx[i-1];
				int nextY = curY + dy[i-1];
				if (nextX < N && nextY < N && nextX >= 0 && nextY >= 0) {
					
					switch (i) {
					case 1: // UP
						if ((curDir == 0 && nextY > 0 && map[nextY-1][nextX] != '1')  // 수직  
								|| (curDir == 1 && map[nextY][nextX-1] != '1' && map[nextY][nextX] != '1' && map[nextY][nextX+1] != '1')) { // 수평 
							
							if(!visit[nextY][nextX][curDir]) {
								visit[nextY][nextX][curDir] = true;
								q.add(new Logs(nextX, nextY, curDir, cnt+1));
							}
						}else {
							break;
						}
						break;
					case 2: // DOWN
						if ((curDir == 0 && nextY < N-1 && map[nextY+1][nextX] != '1')  // 수직  
								|| (curDir == 1 && map[nextY][nextX-1] != '1' && map[nextY][nextX] != '1' && map[nextY][nextX+1] != '1')) { // 수평 
							
							if(!visit[nextY][nextX][curDir]) {
								visit[nextY][nextX][curDir] = true;
								q.add(new Logs(nextX, nextY, curDir, cnt+1));
							}
						}else {
							break;
						}
						break;
					case 3: // LEFT
						if ((curDir == 0 && map[nextY-1][nextX] != '1' && map[nextY][nextX] != '1' && map[nextY+1][nextX] != '1')  // 수직  
								|| (curDir == 1 && nextX-1 >= 0 && map[nextY][nextX-1] != '1' )) { // 수평 
							
							if(!visit[nextY][nextX][curDir]) {
								visit[nextY][nextX][curDir] = true;
								q.add(new Logs(nextX, nextY, curDir, cnt+1));
							}
						}else {
							break;
						}
						break;
					case 4: // RIGHT
						if ((curDir == 0 && map[nextY-1][nextX] != '1' && map[nextY][nextX] != '1' && map[nextY+1][nextX] != '1')  // 수직  
								|| (curDir == 1 && nextX+1 < N && map[nextY][nextX+1] != '1' )) { // 수평 
							if(!visit[nextY][nextX][curDir]) {
								visit[nextY][nextX][curDir] = true;
								q.add(new Logs(nextX, nextY, curDir, cnt+1));
							}
						}else {
							break;
						}
						break;
					case 5:
						if (curX != 0 && curX != N - 1 && curY != 0 && curY != N - 1) {
							if (curDir == 0) { // 수직
								if (curDir == 0 && map[curY][curX - 1] != '1' && map[curY - 1][curX - 1] != '1' && map[curY + 1][curX - 1] != '1'
										&& map[curY][curX + 1] != '1' && map[curY - 1][curX + 1]  != '1'
										&& map[curY + 1][curX + 1] != '1') {
									curDir = 1;
									if(!visit[nextY][nextX][curDir]) {
										visit[nextY][nextX][curDir] = true;
										q.add(new Logs(nextX, nextY, curDir, cnt+1));
									}
								} else {
									break;
								}
							} else { // 수평
								if (map[curY - 1][curX - 1] != '1' && map[curY - 1][curX] != '1' && map[curY - 1][curX + 1] != '1'
										&& map[curY + 1][curX - 1] != '1' && map[curY + 1][curX] != '1'
										&& map[curY + 1][curX + 1] != '1') {
									curDir = 0;
									if(!visit[nextY][nextX][curDir]) {
										visit[nextY][nextX][curDir] = true;
										q.add(new Logs(nextX, nextY, curDir, cnt+1));
									}
								} else {
									break;
								}
							}
						}
						break;

					}
				
				}
				

			}
		}
        System.out.println("0");
		return;
	}

}

 

 

 참고

- 내 블로그만 참고했다 ㅎㅎㅎㅎ뿌듯 !

https://heedipro.tistory.com/256

백준_로봇_1726[Java]