[백준] 1175번 : 배달 - 자바(JAVA)

 

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

1175번: 배달

 

문제 해석

 

직사각형으로 이루어진 교실에 선물을 배달하고 싶다.

 

지도가 주어지는데 4가지 종류로 식별합니다.

S : 지금 민식이가 있는 위치, 배달을 시작하는 곳이며 1개가 존재

C : 민식이가 반드시 선물을 배달해야 하는 곳. 정확하게 2개 존재

# : 민식이가 갈 수 없는 곳이다.

. : 민식이가 자유롭게 지나갈 수 있는 곳

 

동서남북으로 이동하는데 1분 걸리며 네가지 방향 중 한 방향으로 이동할 수 있다.

멈추지 않고 계속 방향을 바꾸어야 한다.

즉, 두 번 연속으로 이동할 수 없다는 말이다.

만약 선물을 모두 배달할 수 없다면 -1을 출력하고 그렇지 않다면 배달하는 데 걸리는 시간의 최솟값을 출력한다.

 

문제 풀이 전 설계

BFS 탐색문제에서 고려할 것은 같은 위치로 연속해서 지나갈 수 없다는 점이다.

Minsik 클래스를 만들어서 이전에 이동했던 방향을 저장하여 겹치지 않도록 합니다.

 

문제 풀이하면서

 

S -> 최단거리의 C1 탐색  -> C1를 시작점으로 C2로 최단으로 이동하는 거리 탐색

을 하면 최단거리를 구할 수 있을 것이라고 생각했습니다.

 

여기서 한 블록에 대해서 중복으로 방문할 수 있습니다

3 3
#.#
CSC
#.#

위의 예시의 경우에는

왼쪽을 먼저 갔다는 가정하에

(0,1)에 있는 C1을 탐색합니다.  time = 1

이후에 오른쪽으로 이동합니다 ( time = 2)

이후에 오른쪽으로 이동할 수 없습니다! (같은 방향이 중복되기 때문에)

이후에 위, 아래로 이동합니다. (time = 3)

다시 아래, 위로 이동합니다 ( time = 4) , (S를 2번 방문하게 됨)

 

여기서 그러면 Visited [][] 배열을 사용하면 안 되는 건가?라고 생각했습니다.

 

실제로 C를 방문한 경우에만 체크해준다면 Visited = true를 사용하여 탐색하면 예제 1, 2, 3, 4에 대해서는 금방 정답이 출력됩니다.

 

3 36
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#C
.................S..................
C#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

하지만 위와 같은 예제 입력 5의 경우에는 방문 체크를 하는 Visited [][]를 사용하지 않아 오른쪽 왼쪽 탐색을 엄청나게 하게 됩니다.

이로 인해 시간이 엄청나게 걸립니다.

 

따라서 여기서 왼쪽 오른쪽 왔다 갔다 하는 무한루프를 쳐내 주어야 한다고 생각했습니다. 그러는 동시에 같은 곳은 또 방

분할 수 있도록 해야 합니다.

 

어떤 y, x 위치의 블록이 상하좌우 visited를 가지도록 합니다.

즉 visited [y좌표][x좌표][방향]에 대해서 방문 체크를 합니다.

 

그렇게 된다면 왼쪽 오른쪽 왔다 갔다 하는 무한루프도 쳐낼 수 있으며 같은 곳을 또 방문할 수도 있습니다.

 

 

위의 경우에도 반례가 존재합니다.

3 3
.C.
.C.
S..

S -> 최단거리의 C1 탐색  -> C1를 시작점으로 C2로 최단으로 이동하는 거리 탐색하는데

 

S에서 C1을 탐색합니다. 이때 C1으로 갈 수 있는 경우의 수는 2가지입니다.

오른쪽 -> 위 또는 위 -> 오른쪽 

이 2가지 경우의 수에 따라 이후의 답이 달라집니다.

 

만약 오른쪽 -> 위가 선택되었을 때는 C1에서 탐색할 때 이미 위를 탐색했으므로 같은 방향으로 중복 탐색이 불가능합니다.

따라서 왼쪽 또는 오른쪽으로 순회하여 가야 합니다. 

 

하지만 위 -> 오른쪽으로 탐색했을 때는 C1에서 다시 위로 탐색할 수 있으므로 정답을 3으로 끝나게 됩니다.

 

무조건 C를 만나면 C1을 기준으로 탐색하도록 했기 때문에 이런 반례가 생겨났습니다.

 

따라서 이전 경로들도 가능한 경우에는 모두 Queue에 기록되어 있어야 합니다.

그러기 위해서는 C1이 탐색되었는지 C2가 탐색되었는지 아무것도 탐색되지 않았는지 기록하는 Status을 체크하는 부분이 필요했습니다.

따라서 visited [y좌표][x좌표][방향][상태]가 필요했습니다.

 

실패 코드 44%에서 틀림

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_1175_배달 {

	static char[][] board;
	static boolean[][][] visited;
	static int[] dy = { 0, 0, -1, 1 };
	static int[] dx = { -1, 1, 0, 0 };
	static Minsik minsik;
	static int height, width;
	static int result;
	static int deliveryCount;

	static enum Direct {
		Left(0), Right(1), Up(2), Down(3), None(4);

		Direct(int value) {
			this.value = value;
		}

		private final int value;

		public int value() {
			return value;
		}

	}

	static class Minsik {
		int y;
		int x;
		Direct direct;
		int time;
		int visitedCount;
		
		public Minsik(int y, int x, Direct direct, int time) {
			super();
			this.y = y;
			this.x = x;
			this.direct = direct;
			this.time = time;
			this.visitedCount = 0;
		}

		@Override
		public String toString() {
			return "Minsik [y=" + y + ", x=" + x + ", direct=" + direct + ", time=" + time + "]";
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		height = Integer.parseInt(st.nextToken());
		width = Integer.parseInt(st.nextToken());

		board = new char[height][width];
		visited = new boolean[height][width][5];

		String str = null;
		for (int y = 0; y < height; y++) {
			str = br.readLine();
			for (int x = 0; x < width; x++) {
				board[y][x] = str.charAt(x);
				if (board[y][x] == 'S') {
					minsik = new Minsik(y, x, Direct.None, 0);
				}
			}
		}

		BFS();

		if(result ==0 ) {
			System.out.println(-1);
		} else {
			System.out.println(result);
		}
	}

	private static void BFS() {
		Queue<Minsik> bfsQ = new LinkedList<Minsik>();
		bfsQ.add(minsik);		

		outer : while (!bfsQ.isEmpty()) {
			Minsik tempMinsik = bfsQ.poll();
			System.out.println(tempMinsik);
			
			for (int k = 0; k < 4; k++) {
				// 방향이 중복되면 continue
				int direct = tempMinsik.direct.value;
				if (direct == k) {					
					continue;
				}

				int tempY = tempMinsik.y + dy[k];
				int tempX = tempMinsik.x + dx[k];
				if (!isValid(tempY, tempX, k)) {
					continue;
				}

				Direct tempDirect = null;
				
				//		Left(0), Right(1), UP(2), Down(3), None(4);

				switch (k) {
				case 0:
					tempDirect = Direct.Left;
					break;
				case 1:
					tempDirect = Direct.Right;
					break;
				case 2:
					tempDirect = Direct.Up;
					break;
				case 3:
					tempDirect = Direct.Down;
					break;
				}
				
				if (board[tempY][tempX] == 'C') {					
					deliveryCount++;
					
					//이미 방문한 C의 경우 4방향에 대해서 모두 막아서 더이상 방문못하게 함
					
					
					if (deliveryCount == 2) {
						result = tempMinsik.time + 1;
						break outer;
					}
					bfsQ.clear();
					//System.out.println(tempDirect.value);
					//add를 여러개해놔야함.. 어떻게할까이걸?
					for(int l=0; l<4; l++) {
						
					}
					bfsQ.add(new Minsik(tempY, tempX, tempDirect, tempMinsik.time + 1));					
					resetVisitedArray();
					for(int l=0; l<4; l++) {
						visited[tempY][tempX][l] = true;
					}
					continue outer;
					
				}
				
				bfsQ.add(new Minsik(tempY, tempX, tempDirect, tempMinsik.time + 1));
				visited[tempY][tempX][k] = true;
				//visited[tempY][tempX] = true;

			}
		}
	}

	private static void resetVisitedArray() {
		visited = new boolean[height][width][5];		
	}

	private static boolean isValid(int tempY, int tempX, int direct) {
		return (tempY >= 0 && tempX >= 0 && tempY < height && tempX < width && board[tempY][tempX] != '#'
				&& !visited[tempY][tempX][direct]);
	}

}

 

성공 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 배달 백준 1175
public class Main_1175_배달Sol {
	
	static int height, width;					
	static char[][] board;				
	static int answer;						
	
	static int[] dy = {0,0,1,-1};		// 세로방향 이동
	static int[] dx = {1,-1,0,0}; 		// 가로방향 이동
	
	static boolean[][][][] visit;		// [세로좌표][가로좌표][0~3 : 동서남북]
	                                    // [0 방문 X / 1 C1만 방문 / 2 C2만 방문] 
	
	// S와 C의 위치를 담기위한 class
	static class location{
		int y,x;	// 세로, 가로 좌표

		public location(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}

	static location start, c1, c2;
	static boolean isC1Empty;
	
	// BFS 를 위한 정보 class
	static class Player{
		int y,x;	// 세로, 가로 좌표
		int time, dir, status;	// 현재까지 시간, 방향(동서남북 0~3), 배달상태
							    // 배달상태 : 0 방문 X / 1 C1만 방문 / 2 C2만 방문
		
		public Player(int y, int x, int time, int dir, int status) {
			this.y = y;
			this.x = x;
			this.time = time;
			this.dir = dir;
			this.status = status;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st; 
		
		// N, A 배열 입력
		st = new StringTokenizer(br.readLine());
		height = Integer.parseInt(st.nextToken());
		width = Integer.parseInt(st.nextToken());
		
		// 세로N, 가로M만큼 지도 선언 후 입력
		board = new char[height+1][width+1];
		isC1Empty = true;
		for(int i=1; i<=height; i++) {
			String str = br.readLine();
			for (int j=1; j<=width; j++) {
				board[i][j] = str.charAt(j-1);
				if(board[i][j]=='S') {
					start = new location(i,j);
					board[i][j] = '.';
				}
				else if (board[i][j]=='C') {
					// C1 입력 전이면
					if (isC1Empty) {
						c1 = new location(i,j);
						isC1Empty = false;
					}
					// C1 입력 됐으면 C2에 입력
					else {
						c2 = new location(i,j);
					}
					board[i][j] = '.';
				}
			}
		}
		
		// BFS 시작 전 불가능하다고 가정하고 시작
		//answer = IMPOSSIBLE;
		// BFS 시작 전 visit 배열 초기화
		// [세로좌표][가로좌표][0~3 : 동서남북]
		// [0 방문 X / 1 C1만 방문 / 2 C2만 방문]
		visit = new boolean[height+1][width+1][4][3];
		
		// 출발점은 true 찍고 시작
		visit[start.y][start.x][0][0] = visit[start.y][start.x][1][0]
		= visit[start.y][start.x][2][0] = visit[start.y][start.x][3][0] = true;
		
		
		Queue<Player> queue = new LinkedList<>();
		// 출발점 정보 넣기 (방향정보는 0~3과 중복을 막기 위해 임의로 -1을 넣어줌)
		queue.offer(new Player(start.y, start.x, 0, -1, 0));

		while (!queue.isEmpty()) {
			Player tempPlayer = queue.poll();

			// 1. 현재 좌표가 배달지역(C1 or C2) 일 경우 true로 바꿔줌
			// 배달상태(status) : 0 방문 X / 1 C1만 방문 / 2 C2만 방문
			
			// 1-1. 현재 좌표가 C1인 경우
			if (tempPlayer.y == c1.y && tempPlayer.x == c1.x) {
				// 1-1-1. status 가 0 또는 2일 경우 +1 (C1 방문 추가)
				if (tempPlayer.status != 1) tempPlayer.status++;
			}
			// 1-2. 현재 좌표가 C2인 경우
			else if (tempPlayer.y == c2.y && tempPlayer.x == c2.x) {
				// 1-2-1. status 가 0 또는 1일 경우 +2 (C2 방문 추가)
				if (tempPlayer.status <= 1) tempPlayer.status+=2;
			}
			
			// 2. BFS에서 답이 최초로 등장 = 정답
			if (tempPlayer.status == 3) {
				answer = tempPlayer.time;
				break;
			}
			
			// 3. 동서남북 돌면서 Queue에 넣기
			for (int k = 0; k < 4; k++) {
				// 연속으로 같은 방향 이동 불가
				if (tempPlayer.dir == k) continue;
				
				int ny = tempPlayer.y + dy[k];
				int nx = tempPlayer.x + dx[k];

				// 1) 지도범위    2) 이동가능지역('.')    3) visit 여부 확인 후 queue에 넣기
				if (ny>=1 && ny<=height && nx>=1 && nx<=width && board[ny][nx] == '.'
						&& visit[ny][nx][k][tempPlayer.status] == false) {
					visit[ny][nx][k][tempPlayer.status] = true;
					queue.offer(new Player(ny, nx, tempPlayer.time+1, k, tempPlayer.status));
				}
			}
		}
		
		// 답이 없을 경우 -1
		if (answer == 0) answer = -1;
		
		// 정답출력
		bw.write(String.valueOf(answer));
		
		bw.flush();
		bw.close();
		br.close();
	}
		
	
}