배달


백준 [1175] 배달

문제보기
Alt text

풀이방법

너무 복잡하게 풀었나?

  • BFS
  • 주의사항 : 지나갔던 길을 다시 지나갈 수 있다. 물론 C도 포함
  • flag를 0,1,2두고 C를 한번도 지나가지 않았을 땐 0, 1번 C를 지나간 경우는 1, 2번 C를 지나간 경우는 2로 지정했다. 이후 v[flag][dir][][]에 상황별로 체크해서 나눠줬다.

소스코드

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 {
	static int N, M, ans;
	static char[][] map;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static Queue<Del> queue;
	static int[][][][] v;
	static int[][] place;

	static class Del {
		int r;
		int c;
		int time;
		int delCnt;
		int dir;
		int flag; //0:배달x,  1,2 : 배달 장소 구분

		public Del(int r, int c, int time, int delCnt, int dir, int flag) {
			this.r = r;
			this.c = c;
			this.time = time;
			this.delCnt = delCnt;
			this.dir = dir;
			this.flag = flag;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		ans = 987654321;
		queue = new LinkedList<>();
		map = new char[N][M];
		v = new int[3][4][N][M];
		place = new int[2][2];

		int idx = 0;
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
				if (map[i][j] == 'S') {
					queue.add(new Del(i, j, 0, 0, -1, 0));
				} else if (map[i][j] == 'C') {
					place[idx][0] = i;
					place[idx][1] = j;
					idx++;
				}
			}
		}

		delivery();
		if (ans == 987654321) {
			ans = -1;
		}
		System.out.println(ans);
	}

	public static void delivery() {
		while (!queue.isEmpty()) {
			Del q = queue.poll();

			if (q.time >= ans)
				continue;

			for (int k = 0; k < 4; k++) {
				if (q.dir == k)
					continue;
				int x = q.r + dx[k];
				int y = q.c + dy[k];

				if (isRange(x, y) && map[x][y] != '#') {
					if (q.delCnt == 0) { // 한번도 배달하지 않은 경우
						if (v[0][k][x][y] == 0 || v[0][k][x][y] > q.time + 1) {
							if (map[x][y] == 'C') {
								int flag = 0;
								if (x == place[0][0] && y == place[0][1])
									flag = 1;
								else
									flag = 2;
								v[flag][k][x][y] = q.time + 1;
								queue.add(new Del(x, y, q.time + 1, q.delCnt + 1, k, flag));
							} else {
								v[0][k][x][y] = q.time + 1;
								queue.add(new Del(x, y, q.time + 1, q.delCnt, k, q.flag));
							}
						}
					} else { // 배달을 한번 한 경우
						if (v[q.flag][k][x][y] == 0 || v[q.flag][k][x][y] > q.time + 1) {
							v[q.flag][k][x][y] = q.time + 1;
							if (map[x][y] == 'C') {
								if (q.flag == 1) {
									if (x == place[1][0] && y == place[1][1]) { // 다른 C
										ans = Math.min(ans, q.time + 1);
									} else {
										queue.add(new Del(x, y, q.time + 1, q.delCnt, k, q.flag));
									}
								} else if (q.flag == 2) {
									if (x == place[0][0] && y == place[0][1]) { // 다른 C
										ans = Math.min(ans, q.time + 1);
									} else {
										queue.add(new Del(x, y, q.time + 1, q.delCnt, k, q.flag));
									}
								}
							} else {
								queue.add(new Del(x, y, q.time + 1, q.delCnt, k, q.flag));
							}
						}
					}
				}
			}
		}
	}

	public static boolean isRange(int x, int y) {
		return x >= 0 && y >= 0 && x < N && y < M;
	}
}