16928번: 뱀과 사다리 게임
첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으
www.acmicpc.net
이게 왜 BFS임
BFS네!
BFS는 언제 쓸까?
가중치가 없을 때 특정 조건에서 최단 경로를 찾을 때 or 모든 노드를 방문하고자 할 때 사용
*가중치가 있을 때는 우선순위 큐 사용
BFS 시행 과정
1. 시작 노드를 큐에 삽입하고 방문 처리를 한다
2. 큐에서 노드를 꺼내고 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 큐가 빌 때까지 2 반복
로직
1. 1을 q에 넣고, visited[]에 방문 처리
2. q에서 뽑았을 때 위치가 100이 아닐때까지
2-1. q에서 노드 꺼내서 인접한 노드가 될 수 있는 +1~+6이 방문X && 100을 넘지 X
2-1-1 만약 그 노드가 사다리나 뱀위에 있다면
-> 이동 / 이동전, 이동후 노드 visited[]에 방문처리, 이동 후 위치와 횟수+1하고 q에 삽입
2-1-2. 그렇지 않다면
-> 인접 노드 방문처리, q에 인접 노드 위치와 횟수+1 삽입
4. q.peek의 위치가 100일 때 횟수 출력
코드
|
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
68
|
/*
백준 16928번: 뱀과 사다리 게임
start : 2023-04-27 15:06
end : 2023-04-27 16:45
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class node {
public int x, d;
node(int x, int d){
//x=위치, d는 이 위치까지 오면서 주사위를 굴린 횟수
this.x = x;
this.d = d;
}
}
public class BJ_16928 {
static int n, m;
static ArrayList<Integer> arr1 = new ArrayList<Integer>();
static ArrayList<Integer> arr2 = new ArrayList<Integer>();
static Queue<node> q = new LinkedList<>();
static boolean[] visited = new boolean[101];
public static void main (String args[]) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
//arr1은 이전 위치, arr2는 이동 후 위치
for (int i=0 ; i <n+m ; i++) {
st = new StringTokenizer(bf.readLine());
arr1.add(Integer.parseInt(st.nextToken()));
arr2.add(Integer.parseInt(st.nextToken()));
}
q.offer(new node(1, 0));
visited[1] = true;
while (q.peek().x!=100){
node cur = q.poll();
for (int i = 1 ; i < 7 ; i ++) {
if (cur.x+i <=100 && !visited[cur.x + i] ) {
//현재 위치가 뱀이나 사다리 위에 있다면 이동하고 q에 넣기
if (arr1.contains(cur.x + i)) {
visited[cur.x + i] = true;
visited[arr2.get(arr1.indexOf(cur.x + i))] = true;
q.add(new node (arr2.get(arr1.indexOf(cur.x + i)), cur.d+1));
} else {
visited[cur.x + i] = true;
q.add(new node (cur.x + i, cur.d+1));
}
}
}
}
System.out.println(q.peek().d);
}
}
|
cs |
참고자료
https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
댓글