coding test

[파이썬, Java] 16928. 뱀과 사다리 게임

잔망루피 2021. 10. 19. 19:26

문제

뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.

주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?

게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.

플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다.

게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.

게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자.

입력

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.

다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.

1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

출력

100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력한다.

예제 입력 1 

3 7

32 62

42 68

12 98

95 13

97 25

93 37

79 27

75 19

49 47

67 17

예제 출력 1 

3

  1. 5를 굴려 6으로 이동한다.
  2. 6을 굴려 12로 이동한다. 이 곳은 98로 이동하는 사다리가 있기 때문에, 98로 이동한다.
  3. 2를 굴려 100으로 이동한다.

예제 입력 2 

4 9

8 52

6 80

26 42

2 72

51 19

39 11

37 29

81 3

59 5

79 23

53 7

43 33

77 21

예제 출력 2 

5

  1. 5를 굴려 6으로 이동하고, 사다리를 이용해 80으로 이동한다. 
  2. 6을 굴려 86으로
  3. 6을 또 굴려 92로
  4. 6을 또 굴려 98로 이동하고
  5. 2를 굴려 100으로 이동한다.

 

 

🎨 나의 풀이

import java.io.*;
import java.util.*;

class Main {
    static HashMap<Integer, Integer> map=new HashMap<>();
    static int[] boardCnt=new int[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 n=0; n<N; n++){         // 사디리 등록
            st=new StringTokenizer(br.readLine());
            int from=Integer.parseInt(st.nextToken());
            int to=Integer.parseInt(st.nextToken());
            map.put(from, to);
        }
        for(int m=0; m<M; m++){        // 뱀 등록
            st=new StringTokenizer(br.readLine());
            int from=Integer.parseInt(st.nextToken());
            int to=Integer.parseInt(st.nextToken());
            map.put(from, to);
        }

        bfs();
        System.out.println(boardCnt[100]);
    }

    public static void bfs(){
        Deque<Integer> deque=new LinkedList<>();
        boolean[] visited=new boolean[101];
        deque.add(1);
        visited[1]=true;
        while(!deque.isEmpty()){
            int pos=deque.pollFirst();
            if(pos > 100){
                break;
            }
            for(int i=1; i<7; i++){
                int newPos=pos+i;
                if(newPos <= 100 && !visited[newPos]){
                    if(map.containsKey(newPos)){    // 사다리 또는 뱀
                        if(!visited[map.get(newPos)]){
                            visited[map.get(newPos)]=true;
                            boardCnt[map.get(newPos)]+=boardCnt[pos]+1;
                            deque.add(map.get(newPos));
                        }
                    }else{
                        visited[newPos]=true;
                        deque.add(newPos);
                        boardCnt[newPos]+=boardCnt[pos]+1;
                    }
                }
            }
        }
    }
}

BFS

다른 사람의 풀이를 참고해서 완성했다.

사다리 또는 뱀이 있는 위치를 밟으면 map에 저장한 값으로 이동한다.

32번에 사다리가 있고, 62번으로 이동한다면 62번을 방문한다.(visited[map.get(newPos)]=true;)

첨에 32번을 방문 처리하고 62번을 데큐에 넣는 실수를 했다.

newPos까지 오는데 주사위를 던진 횟수는 pos(=newPos-i)까지 오는데 주사위를 던진 횟수+1이다.

boardCnt[newPos]+=boardCnt[pos]+1;에 해당함.

이제 보니 +=이 아닌 =을 써야한다.

모든 위치는 한 번만 방문하기 때문이다.

 

 

# 실패
import sys
input=sys.stdin.readline

N, M=map(int, input().split())  # 사다리의 수, 뱀의 수
ladder=[list(map(int, input().split())) for _ in range(N)]     # 사다리 x, y
snake=[list(map(int, input().split())) for _ in range(M)]      # 뱀 u, v

ladder=sorted(ladder, key=lambda x : x[1], reverse=True)       # 도착이 더 빠른 순으로
pos=1
cnt=0

def dfs(pos, cnt) :
    if pos >= 100 :
        print(cnt)
        return 0

    for i in range(6, 0, -1) :
        if pos+i not in snake :     # 뱀 피하기
            if dfs(pos+i, cnt+1) == 0 :
                return 0

def toLadder(tmp_pos, tmp_cnt) :
    global pos, cnt
    if tmp_pos == ladder[0][0] :
        pos=ladder[0][1]
        cnt=tmp_cnt
        return 0
    else :
        for i in range(6, 0, -1) :
            if tmp_pos+i not in snake :
                if tmp_pos+i <= ladder[0][0] :
                    if toLadder(tmp_pos+i, tmp_cnt+1) == 0 :
                        return 0


toLadder(1, 0)
dfs(pos, cnt)

DFS

문제의 테케는 통과했지만...

toLadder 함수에서 1부터 가장 멀리 가는 사다리의 시작 위치까지 주사위를 굴려서 간다.

dfs 함수에서는 뱀을 피하면서 100까지 간다.

위 풀이의 허점은 무조건 가장 멀리 가는 사다리를 선택하는 게 주사위를 최소로 굴리는 것을 보장하지 않는다.

사다리끼리 별로 차이가 나지 않으면 작은 사다리 여러 번 타는 게 더 낫다.

모든 경우를 다 탐색하는 식으로 풀었어야 했다.

 

 

🐊 다른 사람 풀이

# https://donghak-dev.tistory.com/178?category=904697
from collections import defaultdict
import heapq

N, M=map(int, input().split())  # 사다리의 수, 뱀의 수

move=defaultdict(int)

for _ in range(N) :
    x, y=map(int, input().split())
    move[x]=y

for _ in range(M) :
    x, y=map(int, input().split())
    move[x]=y

Q=[]
heapq.heappush(Q, [0, 1])	# [주사위 굴린 횟수, 현재 위치]
answer=1e9
visited=[0]*101
visited[1]=1

while Q :
    now_count, now=heapq.heappop(Q)
    if now == 100 :
        answer=min(now_count, answer)
        break
    for i in range(1, 7) :
        if now+i < 101 :
            if visited[now+i] == 0 :
                if now+i in move.keys() :	# 사다리 또는 뱀
                    heapq.heappush(Q, [now_count+1, move[now+i]])
                    visited[now+i]=1
                else :
                    heapq.heappush(Q, [now_count+1, now+i])
                    visited[now+i]=1

print(answer)

BFS

딕셔너리의 키에 사다리와 뱀이 있는 위치를 넣는다.

딕셔너리의 값은 사다리와 뱀을 타면 도착하는 위치다.

사다리와 뱀을 따로 분리해서 생각해야 하는 줄 알았는데 아니구나!!

heap으로 주사위를 최소로 굴린 곳을 pop한다.

heap을 써서 여러가지 경우 중 가장 최소인 것을 고를 수 있구나

 

 

# https://yunaaaas.tistory.com/84
from collections import deque

def bfs() :
    queue=deque([1])
    visited[1]=True
    while queue :
        now=queue.popleft()
        for move in range(1, 7) :
            check_move=now+move
            if 0 < check_move <= 100 and not visited[check_move] :
                if check_move in ladder.keys() :
                    check_move=ladder[check_move]
                if check_move in snack.keys() :
                    check_move=snack[check_move]
                if not visited[check_move] :
                    queue.append(check_move)
                    visited[check_move]=True
                    board_cnt[check_move]=board_cnt[now]+1

if __name__ == '__main__' :
    N, M=map(int, input().split())
    board_cnt=[0]*101
    visited=[False]*101

    snack=dict()
    ladder=dict()
    for _ in range(N) :
        i, j=map(int, input().split())
        ladder[i]=j
    for _ in range(M) :
        i, j=map(int, input().split())
        snack[i]=j

    bfs()
    print(board_cnt[100])

BFS

뱀과 사다리를 합쳐서 딕셔너리에 담아도 된다.

 

 

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] snakeAndLadder=br.readLine().split(" ");
        int snakeN=Integer.parseInt(snakeAndLadder[0]);
        int ladderN=Integer.parseInt(snakeAndLadder[1]);
        int[] map=new int[101];
        int[] mapCnt=new int[101];
        int x=1;

        Queue<Integer> que=new LinkedList<Integer>();
        que.add(x);
        mapCnt[1]=0;

        for(int i=0; i<snakeN+ladderN; i++){
            String[] startEnd=br.readLine().split(" ");
            map[Integer.parseInt(startEnd[0])]=Integer.parseInt(startEnd[1]);
        }

        while(!que.isEmpty()){
            int top=que.poll();
            for(int i=1; i<=6; i++){
                if(top+i > 100)
                    continue;
                if(map[top+i] == 0 && mapCnt[top+i] == 0){	// 방문한 적 없는 위치
                    mapCnt[top+i]=mapCnt[top]+1;
                    que.add(top+i);
                }else if(map[top+i] != 0 && mapCnt[map[top+i]] == 0){	
                // 뱀 또는 사다리, 방문한 적 없는 위치
                    mapCnt[top+i]=mapCnt[top]+1;	// 뱀 또는 사다리 시작 위치
                    mapCnt[map[top+i]]=mapCnt[top]+1;	// 뱀 또는 사다리 도착 위치
                    que.add(map[top+i]);
                }
            }
        }
        System.out.println(mapCnt[100]);
    }
}

BFS 풀이

앞에 풀이들과 크게 다른 점은 없다.

 

 

문제 출처 👉 백준

 

 

반응형

'coding test' 카테고리의 다른 글

[파이썬, Java] 9205. 맥주 마시면서 걸어가기  (0) 2021.10.20
[파이썬, Java] 2493. 탑  (0) 2021.10.19
[파이썬, Java] 11659. 구간 합 구하기 4  (0) 2021.10.18
[파이썬, Java] 2661. 좋은수열  (0) 2021.10.18
[파이썬, Java] 행렬 테두리 회전하기  (0) 2021.10.13

'coding test'의 다른글

  • 현재글[파이썬, Java] 16928. 뱀과 사다리 게임

관련글

티스토리툴바