이 글은 단순히 답을 적은 글이 아닌 답을 도출해내는 과정을 포함한 글입니다.
정답이 아닌 코드가 중간에 포함되어 있으니 정답 코드를 원하시는 분께선 맨 아래쪽으로 스크롤해주시기 바랍니다.
https://www.acmicpc.net/problem/3197
3197번: 백조의 호수
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
www.acmicpc.net
문제 설명
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는지 계산하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
출력
첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.
문제 풀이 과정
문제를 보고 직사각형 모양의 맵을 숫자로 변환시켜야 한다는 생각이 들었다.
예를 들자면 왼쪽의 맵을 오른쪽과 같이 변환시켜야 한다.
....... 0000000
.XXXXX. 0111110
.XXXXX. 0122210
.XXXXX. -> 0123210
.XXXXX. 0122210
.XXXXX. 0111110
....... 0000000
우선 맵을 전부 스캔하고 '.'과 'L'이 있는 위치를 전부 0 값으로 큐에 집어넣는다.
그 후 큐에서 위치를 하나씩 꺼내며 주변의 위치 중 값이 정해지지 않은 위치들을 현재 값 + 1로 지정하고 큐에 집어넣는다.
이렇게 하면 맵을 숫자로 변환시킬 수 있을 것 같다.
근데 가로, 세로 크기가 최대 1500이라 제대로 최적화하지 않으면 시간 초과가 날 것 같다.
맵을 전체적으로 스캔하며 주변에 물이 있는 얼음을 녹여주는 방법과, 물을 큐에 넣고 하나씩 빼면서 주변의 얼음을 녹여주는 2가지의 방식이 있는데, 첫 번째 방법의 경우 맵이 커질 경우 다음 날이 될 때마다 맵을 일일이 스캔해줘야 하기 때문에 부적합하다.
조금 더 고민해본 결과 맵을 숫자로 변환시킬 필요는 없다는 결론이 나왔다. 알고리즘을 다음과 같이 작성하면 숫자로 변환하지 않고도 문제를 해결할 수 있을 것 같다.
구상한 알고리즘은 다음과 같다.
- 맵을 입력받으며 '.'과 'L'이 있다면 해당 위치를 큐에 넣으며 cnt를 증가시킨다. 'L'의 위치는 따로 변수에 저장한다.
- 결과가 나올 때까지 아래의 과정을 반복한다.
- 'L'의 위치로부터 이동할 수 있는 곳을 스캔한다.
- 만약 범위를 넓히던 중 다른 'L'의 위치에 도달했다면 현재 날짜를 반환하고 종료한다.
- 도달하지 못했다면 날짜를 1 증가시키고, 현재 큐의 길이만큼 아래의 과정을 반복한다.
- 큐에서 위치 하나를 꺼낸다. 꺼낸 위치 주변의 얼음을 녹이고, 큐에 추가한다.
코드를 작성하기 전에 맵을 1차원 배열로 할지 2차원 배열로 할지 정해야 한다.
각자의 장단점은 다음과 같다.
1차원 배열
- 큐에 좌표 형태로 집어넣을 필요가 없기 때문에 큐에 위치를 넣고 뺄 때 속도가 비교적 빨라진다.
- 자신의 양옆은 상관없지만 위/아래의 위치를 구할 때마다 WIDTH 변수 값을 참조해야 한다.
- 코드가 이해하기 힘들어진다.
- 맵의 끝에 도달했는지 체크할 때 나누기, 나머지 연산을 사용하기 때문에 속도가 그만큼 느려진다.
2차원 배열
- 큐에 클래스 형태로 집어넣고, 변수가 x, y 2개로 구분되므로 위치를 넣고 뺄 때 속도가 비교적 느려진다.
- 자신의 상/하/좌/우 위치를 얻기가 편하다.
- 코드가 이해하기 쉬워진다.
- 맵의 끝에 도달했는지 체크하기 위해 부등호만 사용하면 되기에 속도가 그만큼 빨라진다.
다른 장단점도 있겠지만 개인적으로 비교해본 결과 2차원 배열로 구현하는 게 더 나을 것 같아 2차원 배열로 구현했다.
구현 후 제출해봤는데 놀랍게도 한 번에 바로 통과하여 코드 수정 과정이 없다.
코드 수정 내역이 없기 때문에 전체 코드는 바로 아래의 최종 코드 영역에 첨부하였다.
대신 주요 코드를 설명하도록 하겠다.
1. 중요 변수 설명
private static final boolean DEBUG = false;
private static char[][] Map; //맵, '.', 'X', 'L'로 구성되어있다.
private static boolean[][] CheckedMap; //백조 범위 체크 맵, 체크 여부에 따라 true, false 가 저장된다.
private static LinkedList<Point> SwanQueue, WaterQueue; //SwanQueue: 백조 범위 테두리, WaterQueue: 물 테두리
private static int WIDTH, HEIGHT; //맵 너비, 높이
private static Point tmpPoint; //다용도 포인트 변수
private static final int[] dirX = {-1, 1, 0, 0}; // 좌/우/상/하로
private static final int[] dirY = {0, 0, 1, -1}; // 움직일때 증가량SwanQueue는 Queue라기보단 Deque에 가깝다.
물 타일은 앞쪽에 저장하고, 물과 인접한 얼음 타일은 뒤쪽에 저장한다.
WaterQueue는 가장 최근에 물이 된 얼음의 위치를 저장한다. 날이 지날 때마다 WaterQueue 주변의 얼음만 녹여주기 위해 만들었다.
2. 맵 초기화 코드
for(int y=0; y<HEIGHT; y++) {
bufferedReader.read(Map[y]);
bufferedReader.read(); // Ignore '\n'
for(int x=0; x<WIDTH; x++) {
if (Map[y][x] != 'X') {
WaterQueue.add(new Point(x, y));
}
if(Map[y][x] == 'L') {
tmpPoint = new Point(x, y);
}
}
}
SwanQueue.add(tmpPoint);
printMap();맵을 가로 줄 단위로 읽어 들인다. 1바이트씩 끊어서 읽는 것보다 1줄 읽고 1줄 처리하는 방식이 더 효율적이라 생각해 이렇게 구현했다.
만약 물이거나 백조가 위치한 자리라면 WaterQueue에 해당 위치를 추가한다.
만약 백조가 위치한 자리라면 tmpPoint에 값을 저장한다.
맵을 모두 스캔하고 큐에 넣은 후, SwanQueue에 백조가 있던 위치를 추가한다.
3. 얼음 녹이기 코드
private static void updateWater() {
for(int t=WaterQueue.size(); t>0; t--) {
tmpPoint = WaterQueue.remove();
printDebugMsg("Water Pop X:" + tmpPoint.x + " Y:" + tmpPoint.y);
for(int d=0; d<4; d++) {
int x = tmpPoint.x + dirX[d];
int y = tmpPoint.y + dirY[d];
if(x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT) continue;
if(Map[y][x] == 'X') {
Map[y][x] = '.';
WaterQueue.add(new Point(x, y));
}
}
}
}updateWater 함수는 물 주변의 얼음을 1칸 녹여주는 역할을 한다.
WaterQueue엔 항상 전날에 물이 된 얼음들의 위치를 담고 있다.
때문에 WaterQueue에 들어있는 위치 주변의 얼음들을 녹이면 된다.
같은 큐를 쓰기 때문에 미리 위치의 개수를 체크한 뒤 해당 수만큼만 반복하여 얼음이 2번씩 녹는 일이 없도록 방지한다.
4. 백조 이동 범위 업데이트 코드
private static boolean updateSwan() {
for (int t = SwanQueue.size(); t > 0; t--) {
tmpPoint = SwanQueue.remove();
CheckedMap[tmpPoint.y][tmpPoint.x] = true;
printDebugMsg("Swan Pop X:" + tmpPoint.x + " Y:" + tmpPoint.y);
for(int d=0; d<4; d++) {
int x = tmpPoint.x + dirX[d];
int y = tmpPoint.y + dirY[d];
if(x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT) continue;
if(CheckedMap[y][x]) continue;
switch (Map[y][x]) {
case '.':
CheckedMap[y][x] = true;
SwanQueue.push(new Point(x, y));
t++;
break;
case 'X':
CheckedMap[y][x] = true;
SwanQueue.add(new Point(x, y));
break;
case 'L':
return true;
}
}
}
return false;
}얼음 녹이기 코드에 약간의 조건문이 추가되었다고 봐도 무방하다.
SwanQueue엔 전날 백조가 이동 가능한 영역과 맞닿아있는 얼음의 위치를 저장한다.
때문에 SwanQueue에 저장되었던 얼음은 다음날이 되면 항상 물로 변한다.
물로 변하면 백조가 통과할 수 있기에, 그 자리부터 이동 가능 영역을 탐색한다.
백조는 한 번에 한 칸씩만 가는 게 아니라 얼음이 아니라면 어디든 갈 수 있기 때문에 물 타일은 같은 날에 큐에 넣어줘야 한다.
하지만 일반적인 큐처럼 넣으면 맨 뒤에 넣어지기 때문에 다음 날에 녹을 얼음과 섞이게 된다.
때문에 Stack처럼 주변의 물은 가장 앞에 넣는다.
또한 한번 체크한 곳은 다시 체크하지 않도록 체크 확인 배열을 별도로 만들었다.
만약 주변에 백조가 있다면 true를 반환한다.
5. 메인 루프
int day = 0;
initMap();
while (!updateSwan()) {
updateWater();
printMap();
day++;
}
System.out.println(day);맵을 입력받고, 초기화한다.
그 후 백조를 찾을 때까지 얼음을 녹이고, 백조의 이동 가능 영역을 계속 업데이트한다.
이동 가능 영역을 업데이트하다 둘이 만나면 반복문을 종료하고, 여태까지 걸린 일수를 출력한다.
최종 코드
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
public class Main {
private static final boolean DEBUG = false;
private static char[][] Map; //맵, '.', 'X', 'L'로 구성되어있다.
private static boolean[][] CheckedMap; //백조 범위 체크 맵, 체크 여부에 따라 true, false 가 저장된다.
private static LinkedList<Point> SwanQueue, WaterQueue; //SwanQueue: 백조 범위 테두리, WaterQueue: 물 테두리
private static int WIDTH, HEIGHT; //맵 너비, 높이
private static Point tmpPoint; //다용도 포인트 변수
private static final int[] dirX = {-1, 1, 0, 0}; // 좌/우/상/하로
private static final int[] dirY = {0, 0, 1, -1}; // 움직일때 증가량
private static void printMap() {
if(DEBUG) {
for (char[] line : Map) {
System.out.println(line);
}
System.out.println();
}
}
private static void printDebugMsg(String msg) {
if(DEBUG) {
System.out.println(msg);
}
}
private static void initMap() throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String str = bufferedReader.readLine();
HEIGHT = Integer.parseInt(str.split(" ")[0]);
WIDTH = Integer.parseInt(str.split(" ")[1]);
printDebugMsg("Width: " + WIDTH + ", HEIGHT: " + HEIGHT);
Map = new char[HEIGHT][WIDTH];
CheckedMap = new boolean[HEIGHT][WIDTH];
SwanQueue = new LinkedList<>();
WaterQueue = new LinkedList<>();
for(int y=0; y<HEIGHT; y++) {
bufferedReader.read(Map[y]);
bufferedReader.read(); // Ignore '\n'
for(int x=0; x<WIDTH; x++) {
if (Map[y][x] != 'X') {
WaterQueue.add(new Point(x, y));
}
if(Map[y][x] == 'L') {
tmpPoint = new Point(x, y);
}
}
}
SwanQueue.add(tmpPoint);
printMap();
}
private static boolean updateSwan() {
for (int t = SwanQueue.size(); t > 0; t--) {
tmpPoint = SwanQueue.remove();
CheckedMap[tmpPoint.y][tmpPoint.x] = true;
printDebugMsg("Swan Pop X:" + tmpPoint.x + " Y:" + tmpPoint.y);
for(int d=0; d<4; d++) {
int x = tmpPoint.x + dirX[d];
int y = tmpPoint.y + dirY[d];
if(x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT) continue;
if(CheckedMap[y][x]) continue;
switch (Map[y][x]) {
case '.':
CheckedMap[y][x] = true;
SwanQueue.push(new Point(x, y));
t++;
break;
case 'X':
CheckedMap[y][x] = true;
SwanQueue.add(new Point(x, y));
break;
case 'L':
return true;
}
}
}
return false;
}
private static void updateWater() {
for(int t=WaterQueue.size(); t>0; t--) {
tmpPoint = WaterQueue.remove();
printDebugMsg("Water Pop X:" + tmpPoint.x + " Y:" + tmpPoint.y);
for(int d=0; d<4; d++) {
int x = tmpPoint.x + dirX[d];
int y = tmpPoint.y + dirY[d];
if(x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT) continue;
if(Map[y][x] == 'X') {
Map[y][x] = '.';
WaterQueue.add(new Point(x, y));
}
}
}
}
public static void main(String[] args) throws IOException {
int day = 0;
initMap();
while (!updateSwan()) {
updateWater();
printMap();
day++;
}
System.out.println(day);
}
}
질문이나 개선사항은 언제든지 댓글로 남겨주세요.
이상으로 포스팅을 마치겠습니다.
'Algorithm' 카테고리의 다른 글
| [Algorithm] 1655번: 가운데를 말해요 (0) | 2021.06.20 |
|---|---|
| [Algorithm] 12865번: 평범한 배낭 (0) | 2021.06.19 |
