728x90
반응형
3197 - 백조의 호수
https://www.acmicpc.net/problem/3197

문제
두 마리 백조 호수에 살고 있지만 호수를 덮고 있는 빙판으로 만나지 못함
호수 행 R개, 열 C개인 직사각형 모양/ 어떤 칸 얼음으로 덮여있음
호수 차례대로 녹는데 매일 물 공간과 접촉한 모든 빙판 공간 녹음
-> 두 개 공간 접촉하려면 가로 or 세로 닿아 있는 것만(대각선 X) 생각
백조는 물 공간에서 가로 or 세로(대각선 X) 이동 O
=> 며칠 지나야 백조들이 만날 수 있는지
입력
첫째 줄: R, C (1 <= R, C <= 1500)
다음 R개 줄: 각각 길이 C의 문자열 주어짐('.' 물 공간 / 'X' 빙판 공간 / 'L' 백조가 있는 공간)
출력: 주어진 걸리는 날
풀이
이중 BFS
- 백조 이동(`moveSwan()`)
- 백조 물(`.`) 위로만 이동
- 얼음(`X`) 못가지만 내일 녹을 가능성 O -> 다음 큐에 저장
- 얼음 녹이기(`melt()`)
- 물(`.`) 주변의 얼음 녹임
- 녹은 칸(`X`)은 내일의 물(`nextWaterQ`)로 이동
=> 매일 반복
int day = 0;
while (true) {
if (moveSwan()) {
System.out.println(day);
return;
}
melt();
day++;
}
입력
- `map[i][j] != 'X'`: 현재 얼음 X = 물(`.` or `L`) -> `waterQ.offer(new int[]{i, j})`
- 백조(`L`) 좌표 저장 -> `map[i][j] = '.'` => 백조인 경우도 물로 취급
백조 이동
- `swanQ`: 오늘 백조 이동
- `nextQ`: 내일 녹으면 건널 수 있는 얼음 앞
static boolean moveSwan() {
while (!swanQ.isEmpty()) {
int[] cur = swanQ.poll();
// 두 백조 만남
if (cur[0] == swan2[0] && cur[1] == swan2[1]) return true;
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
if (visited[nx][ny]) continue;
visited[nx][ny] = true;
// 오늘 이동
if (map[nx][ny] == '.') swanQ.offer(new int[]{nx, ny});
// 내일 이동
else if (map[nx][ny] == 'X') nextSwanQ.offer(new int[]{nx, ny});
}
}
swanQ = nextSwanQ;
nextSwanQ = new LinkedList<>();
return false;
}
물 녹이기
- `waterQ`: 오늘 물 있는 곳
- `nextWaterQ`: 내일 물 될 곳
static void melt() {
while (!waterQ.isEmpty()) {
int[] cur = waterQ.poll();
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
if (map[nx][ny] == 'X') {
// 얼음 녹음
map[nx][ny] = '.';
// 내일 물
nextWaterQ.offer(new int[]{nx, ny});
}
}
}
waterQ = nextWaterQ;
nextWaterQ = new LinkedList<>();
}
코드
import java.io.*;
import java.util.*;
// 백조의 호수
public class boj_3197 {
static int R, C;
static char[][] map;
static boolean[][] visited;
static Queue<int[]> swanQ = new LinkedList<>();
static Queue<int[]> nextSwanQ = new LinkedList<>();
static Queue<int[]> waterQ = new LinkedList<>();
static Queue<int[]> nextWaterQ = new LinkedList<>();
static int[] swan1, swan2;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static boolean moveSwan() {
while (!swanQ.isEmpty()) {
int[] cur = swanQ.poll();
if (cur[0] == swan2[0] && cur[1] == swan2[1]) return true;
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
if (visited[nx][ny]) continue;
visited[nx][ny] = true;
if (map[nx][ny] == '.') swanQ.offer(new int[]{nx, ny});
else if (map[nx][ny] == 'X') nextSwanQ.offer(new int[]{nx, ny});
}
}
swanQ = nextSwanQ;
nextSwanQ = new LinkedList<>();
return false;
}
static void melt() {
while (!waterQ.isEmpty()) {
int[] cur = waterQ.poll();
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
if (map[nx][ny] == 'X') {
map[nx][ny] = '.';
nextWaterQ.offer(new int[]{nx, ny});
}
}
}
waterQ = nextWaterQ;
nextWaterQ = new LinkedList<>();
}
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];
visited = new boolean[R][C];
int cnt = 0;
for (int i = 0; i < R; i++) {
String s = br.readLine();
for (int j = 0; j < C; j++) {
map[i][j] = s.charAt(j);
if (map[i][j] != 'X') {
waterQ.offer(new int[]{i, j});
}
if (map[i][j] == 'L') {
if (cnt == 0) swan1 = new int[]{i, j};
else swan2 = new int[]{i, j};
cnt++;
map[i][j] = '.';
}
}
}
swanQ.offer(swan1);
visited[swan1[0]][swan1[1]] = true;
int day = 0;
while (true) {
if (moveSwan()) {
System.out.println(day);
return;
}
melt();
day++;
}
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/Union-Find] 백준 4195 - 친구 네트워크 (Java) (0) | 2025.11.10 |
|---|---|
| [BOJ/Union-Find] 백준 1717 - 집합의 표현 (Java) (0) | 2025.11.09 |
| [BOJ] 백준 1655 - 가운데를 말해요 (Java) (0) | 2025.11.06 |
| [BOJ/BFS] 백준 14226 - 이모티콘 (Java) (1) | 2025.06.30 |
| [BOJ/BFS] 백준 17086 - 아기 상어 2 (Java) (0) | 2025.06.28 |