백준 28471번 : W키가 빠진 성원이
이번 문제는 대각선을 포함하여 8 방향 탐색하는 문제의 변형이다.
다시 말해, 8 방향이 아닌 위로 가는 이동을 제외한 7 방향 탐색 문제이다.
좌, 우, 하 + 좌상, 우상, 좌하, 우하 로 이동을 할 수 있으며 최단 거리, 이동 횟수 등을 파악하여 출력하는 문제가 아닌 탐색을 시작했을 때 종료 지점까지 도달할 수 있는 출발점의 개수를 리턴하는 문제이다.
이전까지는 최단거리 이동 횟수를 리턴하는 문제가 대부분이었지만 종료 위치까지 도달할 수 있는 시작 위치의 개수를 리턴하는 문제는 처음이다.
이 문제를 풀기 위해서 생각을 약간 달리해야 한다.
보통은 시작 위치에서 종료 위치까지를 탐색하는 방식으로 접근하지만 이번 문제는 종료 위치에서 부터 시작 위치를 찾아내는 방식으로 접근해야한다.
다시 말해, 종료 위치까지 도달할 수 있는 시작 위치를 파악하는 문제이기 때문에 종료 위치에서부터 탐색을 진행하고서 마지막에 이동할 수 있는 좌표이며, 방문이 가능하면 개수를 세어준다.
우선 멤버 변수로 아래와 같이 선언했다.
1
2
3
4
5
6
public class Main {
static int n, count = 0;
static char[][] arr;
static boolean[][] visited;
static int[] dx = {-1, 0, 0, -1, -1, 1, 1}; // 좌, 우, 하 + 좌상, 우상, 좌하, 우하
static int[] dy = {0, 1, -1, -1, 1, -1, 1}; // 좌, 우, 하 + 좌상, 우상, 좌하, 우하
좌표를 나타내는 dx, dy가 중요한데, 기존 상하좌우에서 대각선을 포함하고 ‘상’으로 이동할 수 있는 좌표를 제외했다.
이로써, 대각선을 포함하고 ‘상’으로 이동이 불가한 방향 배열이 선언된 것이다.
다음으로는 메인 함수이다.
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
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new char[n][n];
visited = new boolean[n][n];
int fx = 0, fy = 0;
for (int i = 0; i < n; i++) {
String line = br.readLine();
for (int j = 0; j < n; j++) {
arr[i][j] = line.charAt(j);
if (arr[i][j] == 'F') {
fx = i;
fy = j;
}
}
}
bfs(fx, fy);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(visited[i][j] && arr[i][j] == '.'){
count++;
}
}
}
System.out.println(count);
}
이 메인 함수에서는 fx, fy를 미리 초기화하여 F 위치를 파악한다.
이 F는 종료 위치로서, 이 위치를 먼저 알아내고 bfs 탐색을 진행할 때 시작 좌표로 넣어주면 된다.
즉, bfs 탐색을 종료 위치를 시작으로 발상을 전환하여 탐색하는 것이다.
이렇게 하면 종료 위치까지 도달할 수 있는 좌표를 알아낼 수 있다.
count를 증가시키기 위한, 개수를 찾기 위한 반복문은 뒤에 다시 얘기하자.
다음은 bfs 탐색인데,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static void bfs(int x, int y) {
visited[x][y] = true;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x, y});
while (!q.isEmpty()) {
int[] cur = q.poll();
int curX = cur[0];
int curY = cur[1];
for (int i = 0; i < 7; i++) {
int nx = curX + dx[i];
int ny = curY + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && arr[nx][ny] != '#') {
q.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
탐색은 기본적인 bfs 탐색 함수이다.
단순히 7 방향을 탐색하고 방문하지 않았고, 벽인 #을 제외한 위치를 탐색한다.
여기서 탐색이 이루어짐에 따라 visited 배열에는 방문 가능한 위치가 true로 표시된다.
이를 활용하여 F까지 도달 가능한 시작 위치를 파악할 수 있다.
1
2
3
4
5
6
7
8
9
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(visited[i][j] && arr[i][j] == '.'){
count++;
}
}
}
System.out.println(count);
다시 메인 함수의 count 증가 반복문을 살펴본다.
앞서 말했듯이 BFS 탐색을 F부터, 종료 지점 부터 시작하면 visited 배열에 F로 도달할 수 있는 위치가 true로 표현된다.
이는 방문할 수 있으며, 해당 좌표가 ‘.’ 이라면 F까지 도달할 수 있는 시작 위치라는 것을 뜻한다.
즉, F까지 도달할 수 있는 ‘.’의 개수를 세어준다면 F까지 도달할 수 있는 시작 위치가 몇 개 인지 파악할 수 있다는 의미이다.
전체 소스코드는 다음과 같다.
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
60
61
62
63
64
65
66
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, count = 0;
static char[][] arr;
static boolean[][] visited;
static int[] dx = {-1, 0, 0, -1, -1, 1, 1}; // 좌, 우, 하 + 좌상, 우상, 좌하, 우하
static int[] dy = {0, 1, -1, -1, 1, -1, 1}; // 좌, 우, 하 + 좌상, 우상, 좌하, 우하
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new char[n][n];
visited = new boolean[n][n];
int fx = 0, fy = 0;
for (int i = 0; i < n; i++) {
String line = br.readLine();
for (int j = 0; j < n; j++) {
arr[i][j] = line.charAt(j);
if (arr[i][j] == 'F') {
fx = i;
fy = j;
}
}
}
bfs(fx, fy);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(visited[i][j] && arr[i][j] == '.'){
count++;
}
}
}
System.out.println(count);
}
static void bfs(int x, int y) {
visited[x][y] = true;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x, y});
while (!q.isEmpty()) {
int[] cur = q.poll();
int curX = cur[0];
int curY = cur[1];
for (int i = 0; i < 7; i++) {
int nx = curX + dx[i];
int ny = curY + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && arr[nx][ny] != '#') {
q.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
}
생각을 조금만 바꾸면 이번 문제를 풀기 쉽다.
그런데 내가 비슷한 문제만 풀다보니 머리가 굳었는지 반대로 생각이 안되서 많이 헤맸다.
알고리즘은 수학적인 사고로 접근해야하는데, 이 수학적인 사고는 유연해야한다고 생각한다.