BOJ) 뱀과 사다리 게임

뱀과 사다리 게임

16928번: 뱀과 사다리 게임

풀이

 

이 문제는 BFS를 활용해 푸는 것이 효율적인 문제다.

딱히 어려운 점은 없었지만, 어이없이 두 번 실수한 부분이 있었다.

첫번째는 while을 통해서 입력받을 때다.

for문을 두 번 쓰자니 번거로울 것 같아서 while로 한번에 받으려고 조건을 넣었었는데, 바보같이 or( || ) 조건이 아니라 and( && ) 조건을 걸었었다.

 

그리고, 처음 시작하는 좌표가 문제에서 1부터라고 제시돼 있었는데, 0부터 시작했던 점이다.

이 두 부분만 고쳐주니까 바로 통과해서 어이가 없었지만, 이런 실수는 하지 말자.. ㅠㅠ

 

처음 문제를 봤을 때는 사실, ArrayList를 사용하려고 했다.

입력받을 때, List에 담아서 뱀을 만나기 전에 사다리로 이동할 수 있는 경우를 가려고 했는데, 뱀을 타는게 더 이득인 경우가 있어서 바로 HashMap으로 변경했다. 이외에는 크게 신경쓴 부분은 없었다.

 

로직을 보면,

1. 입력받은 사다리와 뱀 정보를 각각 HashMap에 저장한다.
2. 1부터 주사위 숫자만큼 더해, 움직이면서 step에 따른 방문 체크를 해준다.
3. 이 때, 해당 위치가 뱀이나 사다리가 연결된 곳이라면, 같은 스텝에 방문 체크를 해주고, 해당 값으로 바꿔준다.
4. 100에 도달한 경우 step을 출력해주고 탐색을 종료한다.

이 4줄로 표시할 수 있을 것 같다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class SnakeLadder_16928 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int ladders = Integer.parseInt(st.nextToken());
        int snakes = Integer.parseInt(st.nextToken());
        HashMap<Integer, Integer> snakeMap = new HashMap<>();
        HashMap<Integer, Integer> ladderMap = new HashMap();

        while(snakes >0 || ladders >0) {
            st = new StringTokenizer(br.readLine());
            if(ladders-- >0) {
                ladderMap.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            } else if(snakes-- >0){
                snakeMap.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }
        }

        solution(snakeMap,ladderMap);

        br.close();
    }

    private static void solution(HashMap<Integer, Integer> snakeMap, HashMap<Integer, Integer> ladderMap) {
        final int MAX = 100;
        final int DICE = 6;
        boolean[][] visit = new boolean[MAX+1][MAX+1];

        LinkedList<MoveInfo> moveList = new LinkedList();

        moveList.offer(new MoveInfo(1,0));

        while(!moveList.isEmpty()) {
            MoveInfo moveInfo = moveList.poll();
            int now = moveInfo.idx;
            int step = moveInfo.step;

            if(now == MAX) {
                System.out.println(step);
                break;
            }
            step++;

            for(int i=1; i<=DICE; i++) {
                int next = now+i;
                if(next <=MAX) { // out of idx 방지
                    if(!visit[next][step]) { // 방문 확인
                        visit[next][step] = true;
                        if(ladderMap.containsKey(next)) {  // 사다리가 있는 경우
                            next = ladderMap.get(next);
                            visit[next][step] = true;
                        } else if(snakeMap.containsKey(next)) { // 뱀이 있는 경우
                            next = snakeMap.get(next);
                            visit[next][step] = true;
                        }
                        moveList.offer(new MoveInfo(next, step));
                    }
                }
            }
        }
    }
}

class MoveInfo {
    int idx;
    int step;

    public MoveInfo(int idx, int step) {
        this.idx = idx;
        this.step = step;
    }
}