백준 25513번 : 빠른 오름차순 숫자 탐색
이번 문제는 5x5 고정된 크기의 보드가 주어지고 보드의 1x1 격자에는 -1, 0, 1, 2, 3, 4, 5, 6 중 하나의 수가 적혀 있으며 1부터 6까지의 숫자를 최단 거리로 순서대로 탐색한 거리를 리턴하는 문제이다.
시작 위치는 보드가 주어진 후 r,c 좌표가 주어진다.
이 때, -1은 방문할 수 없는 위치이며 0은 재방문이 불가능하고 1부터 6까지의 숫자는 재방문이 가능하다.
r,c 좌표부터 시작하여 1부터 6을 순서대로 탐색해야하며 최단 “거리”를 리턴해야한다.
이 문제를 풀기 위해 가장 먼저 메인 함수에 보드를 구체화했다.
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
public class Main {
static int r, c;
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;
arr = new int[5][5];
visited = new boolean[5][5];
for (int i = 0; i < 5; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 5; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
System.out.println(bfs());
}
멤버 변수에 대한 설명은 넘어가고, 보드를 구성하는 로직 역시 매번 하던 것이니 넘어간다.
이 보드를 기준으로 r,c 부터 탐색을 시작해야하기 때문에 bfs로 바로 넘어가자.
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
public static int bfs() {
visited[r][c] = true;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{r, c, 0});
int target = 1;
int move = 0;
while (!q.isEmpty()) {
int[] cur = q.poll();
if (arr[cur[0]][cur[1]] == target) {
if (target == 6) return move + cur[2];
target++;
move += cur[2];
q.clear();
visited = new boolean[5][5];
visited[cur[0]][cur[1]] = true;
q.offer(new int[]{cur[0], cur[1], 0});
continue;
}
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !visited[nx][ny] && arr[nx][ny] != -1) {
if (arr[nx][ny] == 0) visited[nx][ny] = true;
q.offer(new int[]{nx, ny, cur[2] + 1});
}
}
}
return -1;
}
정수 타입을 리턴하는 bfs 함수이다.
가장 처음으로는 시작 위치를 방문 true 체크를 하고 큐에 시작 위치와 거리를 삽입한다.
이후 target은 목표 숫자 (1~6)를 입력하여 갱신하는 변수이고, move는 해당 숫자까지의 거리를 갱신하기 위함이다.
바로 while 반복문으로 진입하여 탐색을 시작한다.
우선 문제에서 주어진 주의사항을 내포한 if 문을 제외하면 단순히 bfs 탐색이다.
다만
1
2
3
4
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !visited[nx][ny] && arr[nx][ny] != -1) {
if (arr[nx][ny] == 0) visited[nx][ny] = true;
q.offer(new int[]{nx, ny, cur[2] + 1});
}
상하 좌우를 탐색하고서 다음 좌표를 큐에 삽입할 때 조건이 필요한데, 이 조건은 앞서 말했듯이 해당 좌표가 0인 경우 재방문이 불가하고 0을 초과하는 경우에는 재방문이 가능해야하기 때문에 정해진 조건이다.
즉, (nx, ny) 다음 좌표에 담긴 숫자가 0이라면 재방문을 막기 위해 해당 위치의 visited 배열을 방문 여부 true 체크를 하고 그 외의 경우 하지 않는다.
이전 조건에서 -1을 걸러주었기 때문에 이런 식으로 로직이 작성되면 1~6이 적힌 좌표는 재방문이 가능하다.
이 부분을 제외하면 나머지는 평범한 bfs 탐색이다.
다시 돌아가 목표까지의 탐색을 위한 조건을 살펴보자.
1
2
3
4
5
6
7
8
9
10
if (arr[cur[0]][cur[1]] == target) {
if (target == 6) return move + cur[2];
target++;
move += cur[2];
q.clear();
visited = new boolean[5][5];
visited[cur[0]][cur[1]] = true;
q.offer(new int[]{cur[0], cur[1], 0});
continue;
}
이 조건 로직은 순서대로 다음과 같다.
- (cur[0], cur[1]) 좌표의 숫자가 목표 숫자와 일치하는지 확인한다.
- 만약 현재 위치의 숫자가 마지막 목표 숫자인 6과 일치하면, 지금까지의 총 이동 횟수인 move에 현재까지의 이동 횟수 cur[2]를 더하고 반환한다.
- 이외의 경우 현재 위치의 숫자가 목표 숫자와 일치하지만 6이 아닌 경우 다음 찾을 숫자를 target++ 로 갱신한다.
- target을 갱신하고 나면 현재까지의 이동 횟수를 총 이동 횟수에 더해준다. 즉, 다음 목표 숫자를 찾기 위한 새로운 탐색을 시작하기 전까지의 총 이동 횟수를 갱신하는 것이다.
- 큐를 clear() 함수로 비워준다. 새로운 목표 숫자를 찾기 위해 탐색을 다시 시작해야하고, 이전까지 탐색한 경로는 더이상 필요하지 않기 때문에 큐를 초기화한다.
- 마찬가지로 방문 여부를 기록하는 visited 배열을 새로 초기화한다.
- 현재 위치한 좌표는 방문한 것이기 때문에 true로 방문 여부를 체크한다. 중복 방문을 방지한다.
- 현재 위치와 이동 횟수를 0으로 초기화한 새로운 배열을 큐에 넣는다. 다음 목표 숫자를 찾기 위한 bfs 탐색의 시작점을 의미한다.
- 반복문의 나머지 부분을 건너뛰고, 큐의 다음 원소에서 bfs 탐색을 계속 진행한다.
이를 통해 각 숫자를 찾을 때마다 탐색을 초기화하고 새로운 목표 숫자에 대한 최소 이동 횟수를 찾을 수 있다.
다음은 전체 소스코드이다.
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
67
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int r, c;
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;
arr = new int[5][5];
visited = new boolean[5][5];
for (int i = 0; i < 5; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 5; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
System.out.println(bfs());
}
public static int bfs() {
visited[r][c] = true;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{r, c, 0});
int target = 1;
int move = 0;
while (!q.isEmpty()) {
int[] cur = q.poll();
if (arr[cur[0]][cur[1]] == target) {
if (target == 6) return move + cur[2];
target++;
move += cur[2];
q.clear();
visited = new boolean[5][5];
visited[cur[0]][cur[1]] = true;
q.offer(new int[]{cur[0], cur[1], 0});
continue;
}
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !visited[nx][ny] && arr[nx][ny] != -1) {
if (arr[nx][ny] == 0) visited[nx][ny] = true;
q.offer(new int[]{nx, ny, cur[2] + 1});
}
}
}
return -1;
}
}
조건 때문에 좀 까다로운 문제였다.
좌표를 재방문할 수 있게 해야하기 때문에 많이 헤맸다.
더구나 목표 숫자가 있고 해당 숫자를 순차적으로 탐색해야하기 때문에 진짜 조건이 까다로웠다.
이번 문제까지 느낀 점은 탐색 문제는 왠만하면 다 비슷한데, 조건에 의해 크게 달라지는 경우가 많다는 것이다.