[파이썬] 백준 12851, 13913 : 숨바꼭질 2, 숨바꼭질 4 (골드4)

[파이썬] 백준 12851, 13913 : 숨바꼭질 2, 숨바꼭질 4 (골드4)

 

12851번: 숨바꼭질 2

 

13913번: 숨바꼭질 4

---

문제

---

풀이

0. 방향성 생각

둘 다 최단거리 문제이다. 한 문제는 더 나아가서 역추적 하는 문제.

최단거리라서 BFS로 푼다.

 

1. BFS 함수 정의

from collections import deque

a,b = map(int,input().split())

def bfs(x,y):
    # 1)
    q = deque()
    q.append(x)
    visit[x] = 1
    time[x] = 0
    
    while q:
        x = q.popleft()
        
        if y == x:
            return time[y],visit[y]
        
        for nx in (x-1,x+1,2*x):  # 2)
            if 0 <= nx < limit:
                if visit[nx] == 0:
                    visit[nx] = visit[x]
                    time[nx] = time[x] + 1
                    q.append(nx)
                else: # 3)
                    if time[nx] == time[x] + 1:
                        visit[nx] += visit[x]

1. 밑에서 다루겠지만 a>b인 평범한 케이스. 첫 입력에 대해서 시간은 0, 방문횟수는 1로 처리한다.
2. 다음 갈 수 있는 경우의 수 3가지에 대해서 범위 내에 있을 때 탐색을 진행한다. 현재 방문횟수가 n번이라고 하면 다음 방문 횟수도 n번이다. 시간은 현재 걸린 시간 +1을 해주면 된다. 첫 방문이면 큐에 추가해준다.
3. 첫 방문이 아닌 경우에는 현재 시간대에서 같은 지점에 접근했는지 확인한다. 만약 같은 시간대에서 같은 지점으로 접근했다면 ( ex : 1->2 (더하기, 곱하기) or 17 19 -> 18 ) 도착지점에 경우의 수에 현재 경우의 수를 더해주면 된다.

 

2. 출력

숨바꼭질2

if a == b:
    print(0)
    print(a)
    
elif a > b:
    print(a-b)
    print(*list(range(a,b-1,-1)))
    
else:
    limit = 10**5+1
    time, visit = [-1]*limit,[0]*limit
    
    path = [b]
    t,v = bfs(a,b)
    print(t)
    while t > 0:
        for i in (b-1, b+1, b//2):
            if 0 <= i < limit:
                if time[i] == t-1:
                    t = t-1
                    path.append(i)
                    b = i
                    break
    print(*path[::-1])

서로 같은 경우나 a가 큰 경우에는 BFS를 돌릴 필요가 없다.

a>b인 경우에만 time, visit을 만들어서 탐색을 진행한다.

도착 지점에서 for문을 돌려서 t-1 시점으로 돌아간다. 하나만 찾아도 시작점으로 돌아갈 수 있으니 하나 찾으면 탈출.

 

숨바꼭질4

if a==b :
    print(0)
    print(1)
elif a>b :
    print(a-b)
    print(1)
else :
    limit = 10**5+1
    time,visit = [-1]*limit, [0]*limit
    print(*bfs(a,b),sep='\n')

서로 같은 경우나 a가 큰 경우에는 BFS를 돌릴 필요가 없다.

a>b인 경우에만 time, visit을 만들어서 탐색을 진행한다.

그냥 리턴값만 사용한다.

---

전체 코드

숨바꼭질 2

from collections import deque

a,b = map(int,input().split())

def bfs(x,y):
    
    q = deque()
    q.append(x)
    visit[x] = 1
    time[x] = 0
    while q :
        x = q.popleft()
        
        if y == x :
            return time[y],visit[y]

        for nx in (x-1,x+1,2*x) :
            if 0<=nx<limit : 
                if visit[nx] == 0 :
                    visit[nx] = visit[x] 
                    time[nx] = time[x] + 1 
                    q.append(nx) 
                else :
                    if time[nx] == time[x]+1:
                        visit[nx] += visit[x]

if a==b :
    print(0)
    print(1)
elif a>b :
    print(a-b)
    print(1)
else :
    limit = 10**5+1
    time,visit = [-1]*limit, [0]*limit
    print(*bfs(a,b),sep='\n')

 

숨바꼭질 4

from collections import deque

a,b = map(int, input().split())

def bfs(x, y):
    q = deque()
    q.append(x)
    visit[x] = 1
    time[x] = 0
    
    while q:
        x = q.popleft()
        
        if y == x:
            return time[y],visit[y]

        for nx in (x-1,x+1,2*x):
            if 0 <= nx < limit:
                if visit[nx] == 0:
                    visit[nx] = visit[x]
                    time[nx] = time[x] + 1
                    q.append(nx)
                else:
                    if time[nx] == time[x] + 1:
                        visit[nx] += visit[x]
if a == b:
    print(0)
    print(a)
    
elif a > b:
    print(a-b)
    print(*list(range(a,b-1,-1)))
    
else:
    limit = 10**5+1
    time, visit = [-1]*limit,[0]*limit
    
    path = [b]
    t,v = bfs(a,b)
    print(t)
    while t > 0:
        for i in (b-1, b+1, b//2):
            if 0 <= i < limit:
                if time[i] == t-1:
                    t = t-1
                    path.append(i)
                    b = i
                    break
    print(*path[::-1])

 

메모리나 시간초과같은 경우는 눈에 보여서 잡을만 한 문제였다.

인덱스 실수나 업데이트때 잘못 업데이트 하는 경우가 더 까다로웠다.