배달
백준 [1175] 배달
풀이방법
너무 복잡하게 풀었나?
- 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;
}
}