728x90
https://www.acmicpc.net/problem/16928
16928번: 뱀과 사다리 게임
첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으
www.acmicpc.net
풀이)
진짜 겁나 틀린 문제...! 꼼꼼히 풀어야 한다는 교훈을 얻었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_BJ_16928_뱀과사다리게임 {
static int[] map = new int[101];
static int[] snakeLadder = new int[101];
static boolean[] visited = new boolean[101];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
snakeLadder[a] = b;
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
snakeLadder[a] = b;
}
bfs();
System.out.println(map[100]);
}//main
private static void bfs() {
Queue<Integer> q = new ArrayDeque<>();
//처음 시작은 무조건 1
q.add(1);
visited[1] = true;
while(!q.isEmpty()){
int cur = q.poll();
//주사위: 한 번에 6칸 이동
for(int i=1; i<=6; i++){
int nx = cur+i;
//다음 좌표가 100보다 작거나 같아야 하고, 방문하지 않았어야함
if(nx <= 100 && !visited[nx]){
//다음 좌표가 사다리를 타고 이동할 수 있을 때 && 이동한 좌표가 방문한 적 없을 때
if(snakeLadder[nx] != 0 && !visited[snakeLadder[nx]]){
// 큐에 저장, 이동 거리 작성, 방문처리
q.offer(snakeLadder[nx]);
map[snakeLadder[nx]] = map[cur] + 1;
map[nx] = map[cur] + 1;
visited[nx] = true;
visited[snakeLadder[nx]] = true;
}
//다음 좌표가 사다리가 없을 때
else if(snakeLadder[nx] == 0){
//다음 좌표 큐에 저장, 이동 거리 작성, 방문처리
map[nx] = map[cur] + 1;
q.offer(nx);
visited[nx] = true;
}
}
}
}//while
}//bfs
}주요 논리는 주석에 작성했다.
처음에는 좀 많이 헤맸는데, 그럴필요 없다는걸 다른 글을 보며 읽었다.
틀린 부분은 질문 게시판의 반례를 보면서 찾았음..ㅠ
담엔 더 꼼꼼히 보자 화이팅!
728x90
'코테 > 백준' 카테고리의 다른 글
| 백준 9663 N-Queen(JAVA) (0) | 2023.01.24 |
|---|---|
| 백준 7662 이중 우선순위 큐(JAVA) (1) | 2023.01.23 |
| 백준 18870 좌표 압축(JAVA) (0) | 2023.01.22 |
| 백준 11723 집합(JAVA) (0) | 2023.01.22 |
| 백준 1764 듣보잡(JAVA) (0) | 2023.01.21 |