문제 정보
3197번: 백조의 호수
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
www.acmicpc.net
핵심
문제 파악
두 마리의 백조가 서로 만나게 되는 날짜를 구하는 문제
- 호수는 물과 얼음으로 이루어져 있고, 물에 인접한(가로, 세로) 얼음은 다음날 녹는다
- 백조는 물 공간에서 가로, 세로로만 이동할 수 있다
- 1 <= R, C <= 1500
생각
물에 인접한 얼음을 하루마다 녹여가면서 날짜를 계산해야 한다 -> 그래프 탐색, BFS(너비 우선 탐색)
처음 백조가 있는 공간 또한 물 공간이다
물을 녹여감과 동시에, 백조가 만날 수 있는지를 계산해야 한다 -> 그래프 탐색
1. 물에 인접한 얼음을 하루마다 녹여 간다
- 맵을 입력받을 때, 물의 위치을 큐에 추가한다
- 큐에서 하나씩 위치를 빼며, 해당 위치 상하좌우의 얼음을 물로 바꾼다
- 얼음이었던 위치를 큐에 집어넣고 다음날부터 2-3을 반복한다
하루마다 물의 위치를 파악하고, 큐에 집어넣는 과정은 비효율적인 방법이므로 이를 개선하기 위하여 다음과 같은 방법을 사용한다.
첫날 큐에 들어간 물에 의해서 녹은, 과정(3)에서 집어넣은 위치(물)는 그 다음날 그 주변 얼음을 녹일 것이다
여기서 중요한 것은, 그 다음날 집어넣은 위치 주변의 얼음만 녹는다는 것이다. 다른 위치에서는 얼음이 녹을 수가 없다.
왜냐하면 첫날에 이미 물 전체의 위치를 큐에 넣고 주변 얼음들을 녹인 후에 큐에 집어넣었기 때문이다.
다만, 얼음이었던 위치를 큐에 집어넣는 연산에서 같은 큐에 집어넣게 되면 while(!queue.isEmpty()) 조건에 의해 반복문이 계속 실행될 것이고, 그렇게 된다면 "하루" 에 진행되어야 할 녹이는 연산을 구분할 수 없게 될 것이다.
이를 다음과 같이 해결하였다
public static void meltIce() {
while(!water.isEmpty()) {
Pos current = water.poll();
for(int[] move: moves) {
int row = current.row + move[0];
int col = current.col + move[1];
// 주변 얼음들을 찾으며, 얼음들을 큐에 삽입함
// 만약 그냥 물이라면, 파악할 필요가 없고 방문 여부를 기록해두지 않는 이유는 방문 여부가 없어도 얼음인지 물인지를 판단하는 과정을 통해
// 중복된 삽입을 하지 않을 수 있기 때문이다
if(Pos.isValidPos(row, col) && map[row][col] == 'X') {
watertmp.add(new Pos(row, col));
map[row][col] = '.';
}
}
}
}watertmp 라는 새로운 큐에 해당 얼음이었던 위치를 집어넣고,
while(백조가 다른 백조를 발견하지 못했다면) {
meltIce();
// 녹은 위치는 다음날 주변 얼음을 녹이기 위해 큐를 대체
water = watertmp;
// 다음날 녹일 얼음들을 다시 집어넣기 위해 재할당
watertmp = new LinkedList<>();
day++;
}이를 하루마다 반복해줌으로써 위 문제점을 해결할 수 있었다
2. 백조가 다른 백조를 찾으려면
백조는 물에서만 이동할 수 있다.
- 백조가 만약 물에서 이동하다가 얼음을 만났다면? 그 얼음은 다음날 녹는 얼음일 것이다 (물과 인접하므로)
- 만약 백조를 만났다면? 그대로 종료시키면 된다
- 물을 만났다면? 하루가 지나지 않았어도 백조는 물에서 자유롭게 이동할 수 있으니 탐색하기 위해 큐에 넣는다
백조가 이동하면서 만나는 얼음들(방문하지 않았던)을 위처럼 기록해둔다면 다음과 같은 장점이 있다
- 백조가 다른 백조를 만나지 못했다고 가정하면, 얼음이 백조를 가로막고 있다는 것이다
- (가정) 오늘 백조를 만나지 못했다면, 주위 얼음이 녹아야 만나러 갈 수 있다
- 만났던 얼음들을 기록해두고, 해당 얼음의 위치부터 탐색하면 (처음 위치에서의) 백조의 이동에 따른 반복을 줄일 수 있다
public static boolean moveSwan() {
while(!swans.isEmpty()) {
Pos current = swans.poll();
for(int[] move: moves) {
int row = current.row + move[0];
int col = current.col + move[1];
if(Pos.isValidPos(row, col) && !visited[row][col]) {
// 방문하지 않은 위치를 방문, 물인 경우 오늘 하루동안 계속 진행할 수 있고, 얼음인 경우 내일까지 기다려야 하므로 다른 Queue에 삽입
visited[row][col] = true;
if(map[row][col] == '.') {
// 물이면? 계속 탐색 가능하므로 swans 큐에 넣는다
swans.add(new Pos(row, col));
} else if(map[row][col] == 'X') {
// 만약 얼음이면? 내일 여기부터 탐색하기 위해 swanstmp 큐에 넣는다
swanstmp.add(new Pos(row, col));
} else if(map[row][col] == 'L') {
// 백조의 위치에 도착했다면 성공, true 반환
return true;
}
}
}
}
return false;
}백조를 만난 경우에는 true를 리턴하기 때문에
int day = 0;
while(!moveSwan()) {
meltIce();
water = watertmp;
swans = swanstmp;
watertmp = new LinkedList<>();
swanstmp = new LinkedList<>();
day++;
}
System.out.println(day);위 반복을 마치고, day를 출력할 수 있다
백조의 이동도 마찬가지로, 얼음들을 새로운 큐에 집어넣고 매번 두 개의 큐를 바꿔주는 방식으로 하루하루 백조의 이동 가능 여부를 판단할 수 있다.
3. 다른 백조를 판단하려면?
백조는 모두 두 마리이다. 따라서 나는 초기에 백조의 위치를 큐에 넣을 때 한마리만 큐에 집어넣었다.
// 백조는 한마리를 기준으로 진행하며 처음 위치를 기록
if(!isFirst) {
swans.add(new Pos(i, j));
visited[i][j] = true;
isFirst = true;
}
백조의 현재 위치의 방문 여부를 true로 바꾸어 주고, 하나만 큐에 넣고 기록하기 위해 isFirst 라는 boolean 타입의 변수를 활용하였다
이렇게 된다면, 해당 백조가 탐색을 진행하다가 다른 백조를 만나면(만날 수 있는 이유는 해당 백조의 visited가 false 이기 때문) 반복을 종료하면 된다.
풀이
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[][] moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
static char[][] map;
static boolean[][] visited;
static Queue<Pos> water = new LinkedList<>();
static Queue<Pos> watertmp = new LinkedList<>();
static Queue<Pos> swans = new LinkedList<>();
static Queue<Pos> swanstmp = new LinkedList<>();
public static int R, C;
public static void main(String[] args) throws IOException{
// 맵을 입력받는 부분
input();
int day = 0;
while(!moveSwan()) {
meltIce();
water = watertmp;
swans = swanstmp;
watertmp = new LinkedList<>();
swanstmp = new LinkedList<>();
day++;
}
System.out.println(day);
}
public static void input() 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];
boolean isFirst = false;
// 맵을 입력받고, 물과 백조의 위치를 큐에 추가
for(int i = 0; i < R; i++) {
String line = br.readLine();
for(int j = 0; j < C; j++) {
map[i][j] = line.charAt(j);
if(map[i][j] == '.') {
water.add(new Pos(i, j));
} else if(map[i][j] == 'L') {
// 백조는 한마리를 기준으로 진행하며 처음 위치를 기록
if(!isFirst) {
swans.add(new Pos(i, j));
visited[i][j] = true;
isFirst = true;
}
// 백조가 있는 위치 또한 물이므로, 추가
water.add(new Pos(i, j));
}
}
}
br.close();
}
public static boolean moveSwan() {
while(!swans.isEmpty()) {
Pos current = swans.poll();
for(int[] move: moves) {
int row = current.row + move[0];
int col = current.col + move[1];
if(Pos.isValidPos(row, col) && !visited[row][col]) {
// 방문하지 않은 위치를 방문, 물인 경우 오늘 하루동안 계속 진행할 수 있고, 얼음인 경우 내일까지 기다려야 하므로 다른 Queue에 삽입
visited[row][col] = true;
if(map[row][col] == '.') {
swans.add(new Pos(row, col));
} else if(map[row][col] == 'X') {
swanstmp.add(new Pos(row, col));
} else if(map[row][col] == 'L') {
// 백조의 위치에 도착했다면 성공, true 반환
return true;
}
}
}
}
return false;
}
public static void meltIce() {
while(!water.isEmpty()) {
Pos current = water.poll();
for(int[] move: moves) {
int row = current.row + move[0];
int col = current.col + move[1];
// 주변 얼음들을 찾으며, 얼음들을 큐에 삽입함
// 만약 그냥 물이라면, 파악할 필요가 없고 방문 여부를 기록해두지 않는 이유는 방문 여부가 없어도 얼음인지 물인지를 판단하는 과정을 통해
// 중복된 삽입을 하지 않을 수 있기 때문이다
if(Pos.isValidPos(row, col) && map[row][col] == 'X') {
watertmp.add(new Pos(row, col));
map[row][col] = '.';
}
}
}
}
}
class Pos {
int row;
int col;
public Pos(int row, int col) {
this.row = row;
this.col = col;
}
public static boolean isValidPos(int row, int col) {
return row >= 0 && row < Main.R && col >= 0 && col < Main.C;
}
}
Source Code on GitHub
댓글