https://www.acmicpc.net/problem/3055
BFS 문제.
물큐를 돌리고, 비버(고슴도치)큐를 돌리면 문제가 해결된다.
코드는 놀랍게도 짰다.
SDS 특강을 2주동안 들으니 나도 모르는 사이 BFS, DFS를 자바로 짤 수 있는 수준이 된 것 같다.
교육듣기 잘하였고 끝까지 참여하길 정말 잘한 것 같다!
그러나 몇가지 치명적인 엣지케이스를 놓쳤다 ㅠㅠ.
1. 비버한테 여러번(여러 시간대에) 도달할 수 있는 경우
2. 물큐돌린 이후 물맵이 전부 0인 경우
엣지케이스를 초반에 고려하고 코드를 짜야할지, 코드를 짜고 엣지케이스를 고려해야할 지에 대한 고민이 필요해보인다.
<내 정답 코드>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int R, C;
static Queue<int[]> waterQ;
static Queue<int[]> biberQ;
static char[][] map;
static int[][] waterMap;
static int[][] biberMap;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
waterQ = new LinkedList<int[]>();
biberQ = new LinkedList<int[]>();
waterMap = new int[R][C];
biberMap = new int[R][C];
String s;
int[] start = new int[] {0, 0};
for(int i=0; i<R; i++) {
s = br.readLine();
for(int j=0; j<C; j++) {
map[i][j] = s.charAt(j);
if (map[i][j] == 'S') {
start = new int[] {i, j};
}
}
}
// 물 bfs 돌리면서 waterMap에 방문시간 마스킹
waterBfs();
// 비버 bfs돌리면서 waterMap 마스킹한 것 참고하여 방문 -> "D"에 도달하면 종료 or 도달불가시 캨터스~
biberBfs(start);
}
static void biberBfs(int[] start) {
biberQ.add(start);
int flag = 0;
while(!biberQ.isEmpty()) {
int[] cur = biberQ.poll();
for(int i=0; i<4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if(nx>=R || ny>=C || nx<0 || ny<0) continue;
if(map[nx][ny] == '.' && biberMap[nx][ny] == 0 && (waterMap[nx][ny] > biberMap[cur[0]][cur[1]] + 1 || waterMap[nx][ny] == 0 )) {
// 비버맵 업데이트, 비버큐에 삽입
biberMap[nx][ny] = biberMap[cur[0]][cur[1]] + 1;
biberQ.add(new int[] {nx, ny});
}
if(map[nx][ny] == 'D') {
biberMap[nx][ny] = biberMap[cur[0]][cur[1]] +1;
System.out.println(biberMap[nx][ny]);
flag = 1;
biberQ.clear();
break;
}
}
}
if(flag==0) System.out.println("KAKTUS");
}
// (a,b)의 좌표에서 시작하는 waterBfs
static void waterBfs() {
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if (map[i][j] == '*') {
waterQ.add(new int[] {i,j});
}
}
}
while(!waterQ.isEmpty()) {
int[] cur = waterQ.poll();
for (int i=0; i<4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if(nx >= R || ny >= C || nx<0 || ny<0) continue;
if(map[nx][ny] == '.' && waterMap[nx][ny] == 0) {
waterMap[nx][ny] = waterMap[cur[0]][cur[1]] +1;
waterQ.add(new int[] {nx, ny});
}
}
}
}
}
'PS > 삼성SDS알고리즘특강' 카테고리의 다른 글
[SDS 알고리즘 특강 복습] 2042 구간 합 구하기 (인덱스트리) (0) | 2025.02.18 |
---|---|
[SDS 알고리즘 특강 복습] 7453 합이 0인 네 정수 (투포인터) (0) | 2025.02.18 |
[SDS 알고리즘 특강 복습] 3020 개똥벌레 (이분탐색 / lowerBound) (0) | 2025.02.17 |
[SDS 알고리즘 특강 복습] 1062 가르침 (DFS / 백트래킹) (0) | 2025.02.16 |
[SDS 알고리즘 특강 복습] 1103 게임 (DFS / 백트래킹 + dp) (0) | 2025.02.15 |