Written by java-style
on 2021-10-07

[백준][JAVA] 1697 : 숨바꼭질

728x90

https://www.acmicpc.net/problem/1697

import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); int[] minTime = new int[100005]; Arrays.fill(minTime, -1); System.out.println(BFS(N, K, minTime)); } public static int BFS(int N, int K, int[] minTime) { int nowN = N; int[] status = new int[3]; Queue queue = new LinkedList(); queue.add(nowN); minTime[nowN] = 0; while (!queue.isEmpty() && nowN != K) { nowN = queue.poll(); status[0] = nowN - 1; status[1] = nowN + 1; status[2] = nowN * 2; for (int i = 0; i < 3; i++) { if (status[i] >= 0 && status[i] <= 100000) { if (minTime[status[i]] == -1) { queue.add(status[i]); minTime[status[i]] = minTime[nowN] + 1; } } } } return minTime[K]; } }

1. main 부

N, K : 수빈이가 있는 위치 N과 동생이 있는 위치 K를 저장할 변수

minTime : 해당 칸까지 가는 데 걸리는 최소 시간을 담은 배열

- Arrays.fills 함수를 사용하여 minTime 의 모든 칸을 -1로 초기화 한다.

- BFS 함수에 N, K 와 minTime 배열을 전달한다.

2. BFS 함수

public static int BFS(int N, int K, int[] minTime) { int nowN = N; int[] status = new int[3]; Queue queue = new LinkedList(); queue.add(nowN); minTime[nowN] = 0; while (!queue.isEmpty() && nowN != K) { nowN = queue.poll(); status[0] = nowN - 1; status[1] = nowN + 1; status[2] = nowN * 2; for (int i = 0; i < 3; i++) { if (status[i] >= 0 && status[i] <= 100000) { if (minTime[status[i]] == -1) { queue.add(status[i]); minTime[status[i]] = minTime[nowN] + 1; } } } } return minTime[K]; } }

- (1)

public static int BFS(int N, int K, int[] minTime) { int nowN = N; int[] status = new int[3]; Queue queue = new LinkedList(); queue.add(nowN); minTime[nowN] = 0;

nowN : nowN에서 다음으로 갈 세 군데의 칸을 탐색한다.

status : 다음에 이동할 index를 저장할 배열

queue : 다음으로 이동한 index를 add 할 queue

- nowN 에는 최초에 수빈이가 있는 위치인 N을 저장한다.

- 수빈이는 한 번에 X-1, X+1, 2*X 중 하나로 이동이 가능하므로 status 는크기가 3인 배열로 선언한다.

- 최초 수빈이가 서있는 자리의 index를 queue 에 add 한다.

- 최초 수빈이가 서있을 때를 0초로 하기 때문에 해당 칸을 0으로 초기화한다.

- (2)

while (!queue.isEmpty() && nowN != K) { nowN = queue.poll(); status[0] = nowN - 1; status[1] = nowN + 1; status[2] = nowN * 2;

- while 종료 조건 : queue가 비었거나 nowN이 K일 경우(동생 칸까지 온 경우)

- queue 에 있는 요소 중 가장 먼저 들어간 것을 꺼내 nowN 을 초기화 시킨다. (최초 poll의 경우 이전과 동일하게 수빈이가 최초 서있는 자리)

- 현재 서있는 곳의 뒤로 한칸, 앞으로 한칸, 순간 이동한 위치를 status 에 차례로 저장한다.

- (3)

for (int i = 0; i < 3; i++) { if (status[i] >= 0 && status[i] <= 100000) { if (minTime[status[i]] == -1) { queue.add(status[i]); minTime[status[i]] = minTime[nowN] + 1; } } } } return minTime[K]; } }

for (int i = 0; i < 3; i++) {

- status 배열을 차례로 순회한다.

if (status[i] >= 0 && status[i] <= 100000) {

- status 배열에 저장한 값의 범위가 배열을 벗어나지 않았는지 확인

ex) 5에서 시작하여 계속 X-1 칸으로 가면 6초 뒤에는 -1 칸을 검사하게 된다.

if (minTime[status[i]] == -1) { queue.add(status[i]); minTime[status[i]] = minTime[nowN] + 1; } } } } return minTime[K]; } }

- 이전에 방문했는지(status[i]칸에 대한 minTime이 -1이 아닌지) 확인 한다.

→ 이전에 방문했다면 현재 방문한 것보다 이전에 방문한 것이 더 빠른 시점이므로 초기화하지 않는다.

- 처음 탐색하는 index라면 queue 에 넣고, 해당 minTime을 전 위치값 +1 을 해준다.

- while 문이 종료되면 minTime[K]를 반환한다.

< 자세한 queue 변화 모습 >

while문을 돌기 전 minTime 배열, queue 모습 / nextN = 5

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

while문을 1바퀴 돌고 난 후 minTime 배열 모습 / nextN = 5

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 -1 -1 -1 -1 1 0 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1

4 6 10

while문을 2바퀴 돌고 난 후 minTime 배열 모습 / nextN = 4

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 -1 -1 -1 2 1 0 1 -1 2 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1

6 10 3 8

while문을 3바퀴 돌고 난 후 minTime 배열 모습 / nextN = 6

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 -1 -1 -1 2 1 0 1 2 2 -1 1 -1 2 -1 -1 -1 -1 -1 -1 -1

1 0 3 8 7 12

while문을 4바퀴 돌고 난 후 minTime 배열 모습 / nextN = 10

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 -1 -1 -1 2 1 0 1 2 2 2 1 2 2 -1 -1 -1 -1 -1 -1 -1

3 8 7 12 9 11 20

(자리 부족으로 19까지만 minTime 배열 표현)

while문을 5바퀴 돌고 난 후 minTime 배열 모습 / nextN = 3

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 -1 -1 3 2 1 0 1 2 2 2 1 2 2 -1 -1 -1 -1 -1 -1 -1

8 7 12 9 11 20 2

while문을 6바퀴 돌고 난 후 minTime 배열 모습 / nextN = 8

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 -1 -1 3 2 1 0 1 2 2 2 1 2 2 -1 -1 -1 3 -1 -1 -1

7 12 9 11 20 2 16

...

while문을 16바퀴 돌고 난 후 minTime 배열 모습 / nextN = 16

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 -1 4 3 2 1 0 1 2 2 2 1 2 2 2 2 4 3 4 2 2

14 13 24 18 22 19 21 40 1 15 17 32

→ 여기서 17의 minTime이 최초로 결정된다. 이후 nextN이 17이 되어 해당 index에 대한 X-1, X+1, 2*X를 탐색 후 while문이 종료되어 minTime[17]이 함수의 return 값으로 반환된다.

728x90

from http://mingmeng030.tistory.com/197 by ccl(A) rewrite - 2021-10-07 22:01:41

Top