[BOJ 백준] 배달(1175) Java

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

1175번: 배달

문제 설명 : 

어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사각형 블록으로 나누어져 있다.

입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다.

• S : 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이다.
• C : 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하게 2개 있다.
• # : 민식이가 갈 수 없는 곳이다.
• . : 민식이가 자유롭게 지나갈 수 있는 곳이다.

민식이가 한 블록 동서남북으로 이동하는데는 1분이 걸린다. 민식이는 네가지 방향 중 하나로 이동할 수 있으며, 교실을 벗어날 수 없다. 민식이가 선물을 배달해야 하는 곳에 들어갈 때, 민식이는 그 곳에 있는 사람 모두에게 선물을 전달해야 한다. 이 상황은 동시에 일어나며, 추가적인 시간이 소요되지 않는다.

민식이는 어느 누구도 자신을 보지 않았으면 하기 때문에, 멈추지 않고 매 시간마다 방향을 바꿔야 한다. 이 말은 같은 방향으로 두 번 연속으로 이동할 수 없다는 말이다. 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 교실의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 교실의 지도가 주어진다.

 

출력 : 

첫째 줄에 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

 

예제 입력 : 

2 3
SCC
...

 

예제 출력 : 

4

 

접근법 : 

1) 어떻게 풀 것인가?

50 * 50 크기의 지도가 주어지고 2 곳에 배달을 하면 되는 문제이다.

여기에 같은 방향으로 연속으로 움직일 수 없다는 제약조건이 있다.

 

문제의 조건이 까다로울땐 조건을 최대한 단순화해서 풀어보고 

제약조건에 맞게 추가하는 것도 한 가지 방법이 된다.

 

① 먼저, 조건을 단순화해 문제를 해결할 수 있는 논리를 세워본다.

만약에 50*50 지도에 1곳만 배달을 하면 되는 문제라면?

 

visit 배열만 지도 크기와 동일한 2차원으로 선언해주고 

보통 BFS로 완전탐색을 진행하면 된다. 

 

② 그런데 연속으로 같은 방향으로 이동할 수 없다.

이 경우 visit 배열에 어느 방향에서 왔는지를 추가해야한다.

 

즉, 기존 visit[세로좌표][가로좌표] 에서 visit[세로좌표][가로좌표][이동한방향] 

3차원으로 추가해서 완전탐색을 진행하면 된다.

 

③ 그런데 배달할 곳이 2군데이다.

이 경우 visit배열에 어떤 곳을 배달했는지를 추가해서 체크해야한다.

 

즉, 기존 visit[세로좌표][가로좌표][이동한방향] 에서

visit[세로좌표][가로좌표][이동한방향][2곳의 방문여부]로

4차원으로 추가해서 완전탐색을 진행하면 된다.

 

이러한 과정을 거치면 아래 소스코드처럼 문제를 해결할 수 있다.

 

 

이 방법 외에도 S→C1 / S→C2 / C1→C2 / C2→C1

을 DP로 구해서 하는 방법도 있을 것 같은데

구현이 까다로워 패스.

 

백트래킹 연습하기 좋은 문제이다.

 

 

2) 시간복잡도

50 * 50 크기에서 BFS를 진행하는데,

가지치기 조건이 충분하므로 (연속 이동 금지)

visit 배열에서 4차원으로 가지치기 한다면 충분할 것으로 예상.

(Java 기준 -  108ms)

 

반대로 연속 방향 또는 2군데 체크하는 가지치기 하지 않으면

Time Out 예상되는 문제.

 

3) 공간복잡도

N 최대 50, M 최대 50으로 충분히 적으므로 고려하지 않음.

 

4) 풀면서 놓쳤던점

맨 처음에 queue에 넣을때, direction을 신경쓰지 않아 오답 발생.

(0 → -1로 수정해서 해결)

 

5) 이 문제를 통해 얻어갈 것

다차원 백트래킹 연습.

이 문제에선 BFS 또는 DFS에서의 다차원 백트래킹이지만, 

DP에서도 많이 활용될 수 있으므로 중요함.

 

Java 코드 : 

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 {
	
	static int N, M;					// N 세로 길이, M 가로 길이
	static char[][] map;				// 지도
	static int ans;						// 정답
	static final int IMPOSSIBLE = 987654321; // 불가능할 경우를 위한 답
	
	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 info{
		int y,x;	// 세로, 가로 좌표
		int time, dir, status;	// 현재까지 시간, 방향(동서남북 0~3), 배달상태
							    // 배달상태 : 0 방문 X / 1 C1만 방문 / 2 C2만 방문
		
		public info(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());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// 세로N, 가로M만큼 지도 선언 후 입력
		map = new char[N+1][M+1];
		isC1Empty = true;
		for(int i=1; i<=N; i++) {
			String str = br.readLine();
			for (int j=1; j<=M; j++) {
				map[i][j] = str.charAt(j-1);
				if(map[i][j]=='S') {
					start = new location(i,j);
					map[i][j] = '.';
				}
				else if (map[i][j]=='C') {
					// C1 입력 전이면
					if (isC1Empty) {
						c1 = new location(i,j);
						isC1Empty = false;
					}
					// C1 입력 됐으면 C2에 입력
					else {
						c2 = new location(i,j);
					}
					map[i][j] = '.';
				}
			}
		}
		
		// BFS 시작 전 불가능하다고 가정하고 시작
		ans = IMPOSSIBLE;
		// BFS 시작 전 visit 배열 초기화
		// [세로좌표][가로좌표][0~3 : 동서남북]
		// [0 방문 X / 1 C1만 방문 / 2 C2만 방문]
		visit = new boolean[N+1][M+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<info> queue = new LinkedList<>();
		// 출발점 정보 넣기 (방향정보는 0~3과 중복을 막기 위해 임의로 -1을 넣어줌)
		queue.offer(new info(start.y, start.x, 0, -1, 0));

		while (!queue.isEmpty()) {
			info cur = queue.poll();

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

				// 1) 지도범위    2) 이동가능지역('.')    3) visit 여부 확인 후 queue에 넣기
				if (ny>=1 && ny<=N && nx>=1 && nx<=M && map[ny][nx] == '.'
						&& visit[ny][nx][i][cur.status] == false) {
					visit[ny][nx][i][cur.status] = true;
					queue.offer(new info(ny, nx, cur.time+1, i, cur.status));
				}
			}
		}
		
		// 답이 없을 경우 -1
		if (ans == IMPOSSIBLE) ans = -1;
		
		// 정답출력
		bw.write(String.valueOf(ans));
		
		bw.flush();
		bw.close();
		br.close();
	}
}