백준 27211번 : 도넛 행성
이번 문제는 n*m 크기의 그래프에서 1은 벽, 0은 땅일 때 1을 제외하고 움직일 수 있는 범위의 개수를 구하는 문제이다.
다만 이전 문제들과는 달리 이 그래프는 “도넛 행성”이라고 해서 그래프의 위쪽 가장자리는 아래쪽 가장자리와, 왼쪽 가장자리는 오른쪽 가장자리와 연결되어 있다.
즉, 원형으로 이루어진 그래프라고 보면 된다.
일단 범위의 개수를 구하는 문제이기 때문에 “도넛”인 것을 제외하고 기존 풀이대로 풀어보았다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, m, count = 0;
static int[][] arr;
static boolean[][] visited;
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0 && !visited[i][j]) {
bfs(i, j);
count++;
}
}
}
System.out.println(count);
}
public static void bfs(int x, int y) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
visited[x][y] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny] && arr[nx][ny] == 0) {
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
}
}
자주 보던 그 알고리즘이다.
이제 “도넛” 형태 인 것을 감안해서 BFS 탐색 시 다음 좌표를 의미하는 nx와 ny의 값을 핸들링할 것이다.
이는, 다음으로 이동할 수 있는 좌표가 가장자리끼리 맞닿아 있기 때문에 경계를 넘어가는 표현을 해주어야하기 때문이다.
해당 알고리즘은 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void bfs(int x, int y) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
visited[x][y] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = (cur[0] + dx[i] + n) % n; // n으로 나눈 나머지를 사용하여 경계를 넘어가는 경우를 처리
int ny = (cur[1] + dy[i] + m) % m; // m으로 나눈 나머지를 사용하여 경계를 넘어가는 경우를 처리
if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny] && arr[nx][ny] == 0) {
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
}
nx와 ny 값에 변화를 준 것이 보인다.
자세히 보면
1
2
int nx = (cur[0] + dx[i] + n) % n; // n으로 나눈 나머지를 사용하여 경계를 넘어가는 경우를 처리
int ny = (cur[1] + dy[i] + m) % m; // m으로 나눈 나머지를 사용하여 경계를 넘어가는 경우를 처리
이 부분인데, 배열의 경계를 넘어가는 경우에 대해 처리하는 것이다.
예를 들어, nx가 0보다 작아진다면 최대 x 좌표인 n을 더해서 n - 1로 만들고, nx가 n 이상이 된다면 n으로 다시 나눈 나머지를 사용해 0으로 만든다.
ny도 동일한 방법이 적용된 것이다.
즉, 어떤 수를 다른 수로 나눈 나머지를 구하는 모듈러 연산을 활용하여 배열의 경계를 순환하는 특성을 구현한 것이다.
조금 더 이해를 위해 아래와 같은 예시를 작성한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = 6, m = 7
상으로 이동 (dx = -1, dy = 0):
현재 위치: (0,0)
이동 후: nx = (0 + (-1) + 6) % 6 = 5, ny = (0 + 0 + 7) % 7 = 0
결과 위치: (5,0)
하로 이동 (dx = 1, dy = 0):
현재 위치: (5,0)
이동 후: nx = (5 + 1 + 6) % 6 = 0, ny = (0 + 0 + 7) % 7 = 0
결과 위치: (0,0)
좌로 이동 (dx = 0, dy = -1):
현재 위치: (0,0)
이동 후: nx = (0 + 0 + 6) % 6 = 0, ny = (0 + (-1) + 7) % 7 = 6
결과 위치: (0,6)
우로 이동 (dx = 0, dy = 1):
현재 위치: (0,6)
이동 후: nx = (0 + 0 + 6) % 6 = 0, ny = (6 + 1 + 7) % 7 = 0
결과 위치: (0,0)
다른 쪽 가장자리로 이동한다고 생각하면 편하다.
전체 소스 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, m, count = 0;
static int[][] arr;
static boolean[][] visited;
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0 && !visited[i][j]) {
bfs(i, j);
count++;
}
}
}
System.out.println(count);
}
public static void bfs(int x, int y) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
visited[x][y] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = (cur[0] + dx[i] + n) % n; // n으로 나눈 나머지를 사용하여 경계를 넘어가는 경우를 처리
int ny = (cur[1] + dy[i] + m) % m; // m으로 나눈 나머지를 사용하여 경계를 넘어가는 경우를 처리
if (!visited[nx][ny] && arr[nx][ny] == 0) {
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
}
}
참고로 BFS에서
1
nx >= 0 && ny >= 0 && nx < n && ny < m
이 조건은 없어도된다.
이미 앞선 모듈러 연산에서 경계 검사가 내재되어 있기 때문이다.
즉, 앞선 연산에서 n혹은 m을 더함으로써 항상 양수 값을 가지게 하고, 결과는 n 혹은 m으로 나눈 나머지를 취하기 때문에 nx와 ny는 항상 0이상, n과 m 미만인 값이된다.
다시 말해, 항상 일정하게 유효 범위 이내에 값이기 때문에 위 조건은 제외해도 된다.
도넛 형태라고 해서 아주 당황했는데, 알고있는 로직으로 먼저 표현한 다음 고민해보니 할만 했다.
이후 이러한 문제가 나오면 모듈러 연산을 사용해야한 다는 것을 기억하기 위해 작성한다.
이 블로그는 저작권자의 CC BY 4.0 라이센스를 따릅니다.