문제 정보
플랫폼 : 백준
분류 : DFS (깊이 우선 탐색), BFS(너비 우선 탐색), 그래프 탐색
난이도 : 골드4
링크 : https://www.acmicpc.net/problem/2573
참고로, 이곳에 문제와 풀이를 올릴 때는 나도 처음 푸는 문제를 올린다! 만약 푼 문제이면 '빙산'이라는 제목 오른쪽에 맞춘 경우 '성공', 틀린 경우 '실패' 가 나온다.
풀이
실버4에서 골드4로 난이도를 높였다. 내가 높은 문제를 풀고 싶었던 것도 있고, 코딩테스트는 보통 낮으면 실버2, 평균 골드4, 높으면 골드2 정도가 나오기 때문이다. (갓카오 제외) 아무튼, 문제를 먼저 이해해보자.
2차원 배열에서 양의 정수는 빙산의 높이이다. 0은 바닷물을 의미한다.
문제 원본은 위 사진이다.
빙산이 바닷물에 영향을 미치는 화살표는 위 사진이다.
그에 따른 1년 후 배열은 그림 2이다. 그림 3은 그림 2로부터 2년 뒤이다. 빙산이 어떻게 깎여나가는지는 빨간 화살표 사진을 보면 된다. 화살표 하나당 빙산의 높이가 1씩 감소된다.
나는 알고리즘 문제를 풀 때, 문제를 보면 막막하다. 하지만, 일단 코드를 작성한다. input 받는 코드라도 입력하고 나면, 문제를 풀 방법이 금방 떠오르곤 한다. (일단 쓰고보자!)
입력을 받았다. 문제에서 요구하는 것이 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성이다. 따라서, 현재 빙산이 몇덩어리인지 구하는 코드를 작성한다.
몇몇 코드가 변경됐다. 처음 코드는 초안이고, 이렇게 바꿔가면서 문제를 풀어나간다. 크게,
1. Point 클래스 추가 (BFS에서 큐에 사용하기 편하기 때문)
2. n, m이 지역변수 -> 전역변수로 승격(?) (이유 동일)
3. dir 전역변수 생성 (현재 빙산에서 상/하/좌/우 에 빙산이 있는지 탐색해야하기 때문)
가 추가됐다. getMassCnt() 메소드에 2차원 배열 map을 넣으면 현재 몇덩어리인지 계산해준다.! 이제 빙산을 녹이는 코드를 작성해보자.
*전역변수는 남발하지 말자! 다른 함수에서도 Write가 발생하는 경우 MT-Safe (Multi Thread - Safe)하지 않을 수 있다!
사진을 보면, 초기에 바닷물의 위치를 기억하는 부분이 있다. (위 사진에서 26~29번째 줄) 나 또한 이런 생각을 했고, 다른 사람도 할 수 있을거라 생각한다.
"그냥 2중 for문 돌면서 현재 바닷물이고, 상하좌우에 빙산이 있으면 -1 해주면 되지 않나?"
아래 반례를 살펴보자.![]
개떡같지만(?) 예시 그림이다...... 원래대로면 1년 뒤에 그림은 아래와 같다.
이제, 2중 for문으로 바닷물을 만날 때마다 1씩 감소시키는 로직을 생각해보자.
보다시피, (1, 1)이 중간에 0이돼서, 2중 for문이 순차적으로 돌면서 (1, 1)도 바닷물로 인식해버렸다!!!!!! 따라서 초기에 바닷물의 좌표를 미리 저장해두고 시작한다.
녹이는 함수, 갯수 구하는 함수를 다 작성했으니, 메인함수에서 정답을 구해보자.
여기까지이다. 제출하니 실행 시간이 1.5초가 걸린다. 이럴 때는 다른 사람의 코드를 보고, 이해하면서 어떻게 시간을 줄여나갔는지 참조해보면 좋다.
코드
import java.util.*;
class Point {
int x, y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}
public class Main {
static int n, m; // 다른 함수에서 접근하기 위해 전역변수로 변경
static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상 하 좌 우
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int answer = 0;
int[][] map = new int[n][m];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
map[i][j] = sc.nextInt();
while(true) {
int massCnt = getMassCnt(map);
if(massCnt >= 2) {
System.out.println(answer);
return;
}else if(massCnt == 0) {
System.out.println(0);
return;
}
melt(map);
answer++;
}
}
public static void melt(int[][] map) {
//바다 위치를 기억해준다.
ArrayList<Point> waterList = new ArrayList<>();
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(map[i][j] == 0) waterList.add(new Point(i, j));
for(Point p : waterList) {
int now_x = p.x;
int now_y = p.y;
for(int i = 0; i < 4; i++) {
//전역변수에서 선언한 dir을 이용해 상하좌우 이동 시도!
int new_x = now_x + dir[i][0];
int new_y = now_y + dir[i][1];
//만약 새로 이동할 좌표가 맵을 벗어나면, 다음 방향으로 continue!
//만약 새로 이동할 좌표가 빙산이 아닌 바닷물이라면, 패스!
if(new_x < 0 || new_y < 0 || new_x >= n || new_y >= m) continue;
if(map[new_x][new_y] == 0) continue;
//빙산을 1씩 녹인다!
map[new_x][new_y]--;
}
}
}
public static int getMassCnt(int[][] map) {
boolean[][] visit = new boolean[n][m];
int cnt = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
//맵 전체를 순회하면서!
if(!visit[i][j] && map[i][j] != 0) {
//방문한 적이 없고, 빙산이라면 (바닷물이 아니라면) 덩어리의 갯수를 1 증가하고 BFS 수행!
cnt++;
Queue<Point> q = new LinkedList<>();
q.add(new Point(i, j));
visit[i][j] = true; // 해당 좌표를 방문처리한다!
while(!q.isEmpty()) {
Point p = q.poll();
int now_x = p.x;
int now_y = p.y;
for(int k = 0; k < 4; k++) {
//전역변수에서 선언한 dir을 이용해 상하좌우 이동 시도!
int new_x = now_x + dir[k][0];
int new_y = now_y + dir[k][1];
//만약 새로 이동할 좌표가 맵을 벗어나면, 다음 방향으로 continue!
//만약 새로 이동할 좌표가 빙산이 아닌 바닷물이라면, 패스!
//새로 이동할 좌표가 이미 방문한 곳이라면, 패스!
if(new_x < 0 || new_y < 0 || new_x >= n || new_y >= m) continue;
if(map[new_x][new_y] == 0) continue;
if(visit[new_x][new_y]) continue;
//새로 이동할 좌표가 맵 안에 있다면, 큐에 넣어주고 방문처리!
q.add(new Point(new_x, new_y));
visit[new_x][new_y] = true;
}
}
}
}
}
return cnt;
}
}
더 많은 정답 코드
블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.
