[백준] 13913, 14226, 13549

숨바꼭질 4 (13913번)

• 사이트/난이도: 골드4 / 백준
• 코드

# 골드4 숨바꼭질 4
import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
MAX = int(1e5)
graph = [0] * (MAX + 1)
move = [0] * (MAX + 1)

def path(now):
    result = []
    temp = now
    for _ in range(graph[now]):
        result.append(temp)
        temp = move[temp]
    return ' '.join(map(str, result[::-1]))

def bfs(start):
    q = deque([start])
    graph[start] = 1    
    while q:
        now = q.popleft()
        if now == k:
            print(graph[now] - 1)
            print(path(now))
            return
        for next in (now-1, now+1, now*2):
            if next < 0 or next > MAX or graph[next] != 0:
                continue
            graph[next] = graph[now] + 1
            move[next] = now
            q.append(next)

bfs(n)

• 느낀점
  • 기존 숨바꼭질 문제에서 경로를 표시하는게 추가된 심화 문제
  • 찾을 때 까지 걸리는 시간은 기존대로 bfs로 풀고 경로는 move라는 배열을 하나 더 만들어서 해당 인덱스가 이전 위치를 기록하는 식으로 하여 풀었다.
  • 근데 처음에는 q 안에다가 기존 위치까지 다 기록하려고 배열을 하나 더 넣어놨는데 그러니 시간초과가 났음..

이모티콘 (14226번)

• 사이트/난이도: 백준 / 골드4
• 코드

# 골드4 이모티콘
import sys
from collections import deque
input = sys.stdin.readline

s = int(input())
visited = dict()
visited[(1,0)] = 0 # {(모니터 이모티콘 개수, 클립 이모티콘 개수): 총 시간}

def bfs():
    q = deque([]) # [(모니터 개수, 클립 개수)]
    q.append((1,0))
    while q:
        m, c = q.popleft()
        if m == s:
            print(visited[(m, c)])
            return
        # 1. 화면에 있는 이모티콘 클립보드에 모두 복사
        if (m, m) not in visited.keys():
            visited[(m,m)] = visited[(m, c)] + 1
            q.append((m, m))
        # 2. 클립보드에 있는 이모티콘 화면에 붙여넣기
        if m+c <= s and (m+c, c) not in visited.keys():
            visited[(m+c, c)] = visited[(m, c)] + 1
            q.append((m+c, c))
        # 3. 화면에 있는 이모티콘 중 하나 삭제
        if m-1 >= 0 and (m-1, c) not in visited.keys():
            visited[(m-1, c)] = visited[(m,c)] + 1
            q.append((m-1, c))

bfs()
print(visited)

• 느낀점
  • dp 혹은 bfs를 통해 풀 수 있는 문제
  • bfs로 풀때 방문 표시 배열을 설정해 놓고 푸는데 이 문제는 해당 인덱스를 설정하는게 특이하다.
  • 인덱스를 (모니터 이모티콘 개수, 클립보드 이모티콘 개수) 로 이용해야한다.
  • 2차원 배열로 할 수 는 있지만 낭비되는 메모리가 많기 때문에 dict의 key를 이용한다.

숨바꼭질 3 (13549번)

• 사이트/난이도: 백준 / 골드 5
• 코드

# 골드5 숨바꼭질 3
import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
MAX = int(1e5)
graph = [-1] * (MAX+1) # 목적지(인덱스)별 걸린 시간

def bfs():
    q = deque([n])
    graph[n] = 0
    while q:
        now = q.popleft()
        if now == k:
            return graph[now]
        for next in (now + 1, now - 1, now * 2):
            if 0 <= next <= MAX and graph[next] == -1:
                if next == now * 2: # 순간이동
                    q.appendleft(next) # 걸리는 시간 0초 이므로 최우선순위를 위해 appendleft
                    graph[next] = graph[now]
                else: # 걸을 때
                    q.append(next)
                    graph[next] = graph[now] + 1

print(bfs())

• 느낀점
  • 숨바꼭질 응용문제 - 순간이동시 0초라서 이점에 유의해야 한다.
  • 일단 순간이동 시 0초가 걸리므로 최우선순위를 위해 appendleft 를 이용한다.
  • 그리고 처음에 풀 때 걸을때와 순간이동때를 나눴는데 now가 1일 때 위치가 2일때는 걸을 때와 순간이동 때가 같다. 하지만 이러면 순간이동때인 0초로 최소값을 해야 되는데 걸을때 1초로 설정되어서 최소값을 못구하게 된다. (여기서 많이 헤멨다.) 이를 해결하기 위해 하나의 포문 안에 조건문을 넣어서 풀어줬다.