[알고리즘/BFS & DFS] 13549번 : 숨바꼭질 3 - python

링크 : https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

---

• 문제
• 소요시간: 42분 36초

---

• 설계하기(접근방법) 

1. 입력받기

숫자를 입력받는다

2. 구현하기

다른 숨바꼭질 문제와 유사하다

핵심은 곱셈의 경우 가중치가 0이기 때문에 처리를 잘 해줘야 한다

곱셈을 먼저 처리하지 않으면

1 -> 2 로 증가시킬 때 시간이 +1이 되기 때문에

오답이 난다

 

3. 출력하기

최소 시간을 출력한다

 

---

• 코드(출력)

from collections import deque

def bfs(x):
    q = deque()
    q.append(x)
    dx = [-1, +1]
    while q:
        x = q.popleft()
        for i in range(2,-1,-1):
            if i < 2:
                nx = x + dx[i]
            else: 
                nx = x * 2
            if 0 <= nx < 100001:
                # 방문하지 않았던 점
                if visited[nx][1] == 0:
                        q.append(nx)
                        # 지금 최소 시간을 넣어준다
                        if i < 2:
                            visited[nx][0] = visited[x][0] + 1
                            visited[nx][1] = 1
                        else:
                            visited[nx][0] = visited[x][0]
                            visited[nx][1] = 1
                # 방문했던 점
                if visited[nx][1] == 1:
                    # 새로운 시간이 더 짧은 경우 그 케이스를 넣어준다
                    if i < 2:
                        if visited[nx][0] > visited[x][0] + 1:
                            visited[nx][0] = visited[x][0] + 1
                    else:
                        if visited[nx][0] > visited[x][0]:
                            visited[nx][0] = visited[x][0]

        

start, target = map(int, input().split())

# 시간, visited
visited = [[0,0] for _ in range(100001)]

visited[start][1] = 1
bfs(start)
print(visited[target][0])

훨씬 좋은 코드를 다시 짰다.

from collections import deque


def bfs(x,y):
    q = deque()
    q. append(x)
    while q:
        x = q.popleft()
        if x == y:
            break
        for i in  [x*2, x -1, x + 1]:
            if 0 <= i < 100001 and visited[i] == -1:
                q.append(i)
                if i == x*2:
                    visited[i] = visited[x]
                else:
                    visited[i] = visited[x] + 1

start, target = map(int, input().split())

visited = [-1 for _ in range(100001)]
visited[start] = 0
bfs(start, target)
print(visited[target])

 

---

• 얻어갈 부분

1. 1 -> 2 로 증가하는 예외 케이스 때문에 피를 봤다. 곱셈 연산을 최우선으로 두어야 이 케이스에서 틀리는 것을 방지할 수 있다.

2. 평소에는 dx를 선언해서 돌았는데 이번에는 for i in [x-1,x+1, x*2] 처럼 리스트를 돌려서 케이스를 처리하기 쉬웠다.

3. 보통 visited를 0을 선언해서 사용했는데, -1로 해도 문제가 없었다. 혹시 필요한 경우 스킬로 사용하자