해당 문제의 원문은 여기서 확인하자.
문제 이해
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 문제이다.
N * N 크기의 땅이 있고, 땅은 1 * 1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
특정 규칙을 만족하는 경우 인구 이동이 발생하며 더 이상의 인구 이동이 없을 때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
- 연합을 해체하고, 모든 국경선을 닫는다.
첫째 줄에 N, L, R이 주어지고, 둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. (r행 c열에 주어지는 정수는 A[r][c]의 값이다.) 제한 사항은 다음과 같다.
- 1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100
- 0 ≤ A[r][c] ≤ 100
- 0 ≤ 결과 ≤ 2,000
접근 방식
BFS의 개념을 이용한 방식과 DFS의 개념을 이용한 방식으로 문제를 해결하였다.
<BFS 방식>
단순하게 매번 BFS 탐색을 통해 규칙에 따라 연합을 만들고 탐색 대상의 좌표에 대한 값을 평균값으로 초기화한다. 중복 탐색을 방지하기 위해 방문 여부를 체크하며, 맵 전체에 대해 BFS 탐색이 종료되면 이전 과정을 다시 반복한다. 최종적으로 인구 이동이 발생하지 않는 경우 해당 반복을 종료한다. 예제를 통해 알아보자.
먼저, 첫번째 10의 위치부터 BFS 탐색을 수행한다. 4방향 탐색을 진행하며 맵의 범위를 벗어나지 않는 경우만을 진행한다. 이때 방문한 곳의 위치는 F에서 T로 바꿔 이후 탐색에서 중복 탐색을 방지한다. 30의 경우 L과 R범위를 초과하기 때문에 탐색을 진행하지 않는다. 따라서 20으로 탐색만이 가능하다.
10은 이미 방문한 곳이기 때문에 20에서 10으로의 탐색은 진행되지 않는다. 5와 15로의 탐색은 유효한 경로 탐색이 진행된다.
먼저 5로의 탐색을 확인해보자. 5에서 30과 60으로의 경로는 범위를 벗어나 불가능하다. 20은 이미 거쳐온 곳(방문)으로 불가능하다. 10의 경우는 범위도 만족하며 처음 방문하는 곳으로 유효하다.
다음은 15에 대해서 탐색을 진행해보자. (해당 순서가 이해가 가지 않는다면 BFS의 개념을 다시 공부하자.) 15에서 30으로 가는 경우는 범위를 벗어나며, 10은 이미 5에서 탐색을 진행하였기 때문에 중복 탐색할 필요가 없다. 따라서 15에서 탐색은 종료된다.
이전 과정들을 반복하면 한 번의 BFS 탐색에서 다음과 같은 결과를 얻을 수 있다.
이제 찾은 영역의 값을 모두 더하고 평균값으로 초기화를 진행하자. (영역의 값은 미리 더해가는 것을 추천한다.)
처음 10에 대해서 BFS 탐색을 진행하였으므로 그 다음 수인 30과 40에 대해서도 순서대로 위의 과정들을 반복한다. 중복 탐색에 유의하여 진행을 하면 다음과 같은 결과를 얻을 수 있다.
지금까지의 과정의 하나의 과정이다. 이 상태에서 인구 이동이 발생한 경우 새로 만들어진 맵을 이용해 처음부터 다시 진행하고, 인구 이동이 발생하지 않은 경우 현재까지 카운트된 인구 이동 횟수를 출력한다.
배열의 크기가 최대 50 * 50의 크기를 지니기 때문에 해당 방법으로도 꽤 빠른 시간 안에 문제를 해결할 수 있지만 효율은 별로 고려되지 않은 상태이다.
<DFS 방식>
BFS 방식과 개념적인 면에선 크게 다르지 않다. DFS 방식으로 국경을 열 수 있는 나라들을 찾고, 그 과정에서 방문한 나라의 수와 나라들의 인구수 총합을 구한다. 이때 방문 여부는 F, T가 아닌 정수로 초기화하며, 국경이 열리지 않은 나라들의 경우 -2로 초기화한다.
위의 예시를 보면 아직 값들이 평균값으로 초기화되지 않은 상태이다. (BFS 방식에선 하나의 연합이 탐색되면 평균값으로 초기화를 진행하였지만 DFS에선 ) 방문 여부는 국경이 열린 나라들의 경우 0이상의 정수, 아닌 경우는 -2로 초기화되었다. (※ 방문 여부의 초기값은 -1로 초기화하고 시작한다.)
탐색을 통해 연합 결성이 완료되고 이제 맵을 다시 하나씩 확인하며 연합 번호에 맞게 미리 저장해둔 평균값으로 초기화(인구 이동)를 진행하였다. 인구 이동이 발생한 경우 이전 과정들을 다시 반복하고, 인구 이동이 발생하지 않은 경우 카운트된 값을 출력한다.
코드
<BFS 방식>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class 백준16134번 {
static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer token;
static int N, L, R;
//4방향 탐색을 위한 정의
static final int[] X = {-1, 1, 0, 0};
static final int[] Y = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
token = new StringTokenizer(br.readLine());
N = Integer.parseInt(token.nextToken());
L = Integer.parseInt(token.nextToken());
R = Integer.parseInt(token.nextToken());
int[][] map = new int[N][N];
//일 수
int count = 0;
//인구 이동 체크를 위한 변수
boolean flag = true;
for (int i = 0; i < N; i++) {
token = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++)
map[i][j] = Integer.parseInt(token.nextToken());
}
while (flag) {
//중복 탐색 방지를 위한 배열
boolean[][] visited = new boolean[N][N];
flag = false;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
//방문한 적이 있으면 탐색 수행 X
if (visited[y][x]) continue;
//인구 이동이 발생한 경우 flag 변경
flag = BFS(map, visited, x, y) ? true : flag;
}
}
//인구 이동이 발생한 경우 카운트 증가
count += flag ? 1 : 0;
}
System.out.println(count);
}
public static boolean BFS(int[][] map, boolean[][] visited, int x, int y) {
//BFS 탐색을 수행할 좌표 저장
Queue<int[]> q = new ArrayDeque<>();
//탐색한 모든 대상들을 저장
Queue<int[]> save = new ArrayDeque<>();
//탐색한 모든 좌표들의 값의 총합
int total = 0;
//시작 위치
q.add(new int[] {x, y});
visited[y][x] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
//방문한 좌표 저장
save.add(cur);
//방문한 좌표의 값 저장
total += map[cur[1]][cur[0]];
//4방향 탐색
for (int i = 0; i < 4; i++) {
//다음 탐색 좌표
int nextX = cur[0] + X[i];
int nextY = cur[1] + Y[i];
//탐색 좌표의 유효성 검사
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
else if (visited[nextY][nextX]) continue;
//탐색 좌표의 값이 조건을 만족하는지 판단
int diff = Math.abs(map[cur[1]][cur[0]] - map[nextY][nextX]);
if (diff < L || R < diff) continue;
//유효한 좌표인 경우 방문 여부 체크와 탐색의 대상으로 저장
visited[nextY][nextX] = true;
q.add(new int[] {nextX, nextY});
}
}
//연합이 생긴 경우
if (save.size() > 1) {
int avg = total / save.size();
//탐색 과정에서 거친 모든 좌표의 값을 초기화
while (!save.isEmpty()) {
int[] cur = save.poll();
map[cur[1]][cur[0]] = avg;
}
//인구 이동 발생 X
return true;
}
//인구 이동 발생 O
return false;
}
}
<DFS 방식>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class 백준16134번 {
static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer token;
static int N, L, R;
static int[][] map, visited;
//4방향 탐색 정의
static final int[] X = {-1, 1, 0, 0};
static final int[] Y = {0, 0, -1, 1};
static int key;
//인덱스 0번 : 탐색 과정에서 방문한 나라들의 인구수 총합
//인덱스 1번 : 탐색 과정에서 방문한 수
static int[] saveValue = new int[2];
public static void main(String[] args) throws IOException {
token = new StringTokenizer(br.readLine());
N = Integer.parseInt(token.nextToken());
L = Integer.parseInt(token.nextToken());
R = Integer.parseInt(token.nextToken());
map = new int[N][N];
visited = new int[N][N];
//평균값 저장
List<Integer> save = new LinkedList<>();
//일 수
int count = 0;
for (int i = 0; i < N; i++) {
token = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++)
map[i][j] = Integer.parseInt(token.nextToken());
}
while (true) {
//방문하지 않은 곳은 -1로 초기화
for (int i = 0; i < N; i++)
Arrays.fill(visited[i], -1);
key = 0;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
//중복 탐색 방지
if (visited[y][x] != -1) continue;
Arrays.fill(saveValue, 0);
DFS(x, y);
//국경선이 열린 경우 평균값을 저장
//국경선이 열리지 않은 경우 해당 위치의 방문 여부를 -2로 초기화(이후 평균값 수정 X)
if (saveValue[1] > 1) {
save.add(saveValue[0] / saveValue[1]);
key++;
} else {
visited[y][x] = -2;
}
}
}
//인구 이동이 발생하지 않은 경우 종료
if (key == 0) break;
//인구 이동 시작(연합에 대해 평균값으로 조정)
for (int y = 0; y < N; y++)
for (int x = 0; x < N; x++)
if (visited[y][x] >= 0)
map[y][x] = save.get(visited[y][x]);
//일 수 카운트 증가
count++;
//저장된 평균값들 제거
save.clear();
}
System.out.println(count);
}
public static void DFS(int x, int y) {
//방문 여부 체크 및 방문 수와 총 인구수 카운트
visited[y][x] = key;
saveValue[0] += map[y][x];
saveValue[1]++;
//4방향 탐색
for (int i = 0; i < 4; i++) {
int nextX = x + X[i];
int nextY = y + Y[i];
//맵의 범위를 벗어났는지 확인
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
//재방문인지 확인
else if (visited[nextY][nextX] != -1) continue;
//탐색에 있어 유효한 범위인지(인구수 차이 범위) 확인
int diff = Math.abs(map[y][x] - map[nextY][nextX]);
if (L <= diff && diff <= R)
DFS(nextX, nextY);
}
}
}'해설서 > Algorithm' 카테고리의 다른 글
| [프로그래머스] 문자열 압축 (0) | 2022.07.29 |
|---|---|
| [백준] 9251번 LCS (0) | 2022.07.28 |
| [백준] 1520번 내리막 길 (0) | 2022.07.24 |
| [백준] 5557번 1학년 (0) | 2022.07.24 |
| [백준] 10026번 적록색약 (0) | 2022.07.22 |
댓글