[백준] 13460번 구슬탈출 2(파이썬)

난이도 : GOLD I

문제링크 : https://www.acmicpc.net/problem/13460

삼성 sw 역량 테스트 문제이다

문제해결

• 해결하지 못해서 다른풀이에서 영감 받았다.
• 파란공과 빨간공 bx,by rx,ry 로 저장한다.
• 구멍이나 벽을 만날 때까지 while True 로 움직인다.
• 파란구슬이 구멍에 빠지면 안되므로 그 경우는 continue로 넘긴다.
• 움직인 후의 빨간공과 파란공의 위치가 같다면 기존 위치에서의 차이로 값을 비교해서 정한다.

소스코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())

graph = []

for _ in range(n):
    graph.append(list(input().strip()))

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

for i in range(n):
    for j in range(n):
        if graph[i][j] == 'B':
            bx = i
            by = j
        elif graph[i][j] == 'R':            
            rx = i
            ry = j
        

q = deque([(rx, ry, bx, by)])
visited = [(rx,ry,bx,by)] #
cnt = 0
while q:
    for _ in range(len(q)): # 
        rx, ry, bx, by = q.popleft()
        if graph[rx][ry] == 'O':
            print(cnt)
            exit()
    
        if cnt > 10:
            print(-1)
            exit()
    
        for i in range(4): 
            rnx = rx
            rny = ry
            bnx = bx
            bny = by
    
            while True: # 
                rnx += dx[i]
                rny += dy[i]
                if graph[rnx][rny] == '#': # 벽을만나면 다시 그전으로 롤백
                    rnx -= dx[i]
                    rny -= dy[i]
                    break
                if graph[rnx][rny] == 'O': #구멍에 빠지면 break
                    break
    
            while True:
                bnx += dx[i]
                bny += dy[i]
                if graph[bnx][bny] == '#':
                    bnx -= dx[i]
                    bny -= dy[i]
                    break
                
                if graph[bnx][bny] == 'O': 
                    break
    
            if graph[bnx][bny] == 'O': #파란공이 구멍에 빠지면
                continue
    
            if rnx == bnx and rny == bny: # 두공이 같은 위치에 있을 경우
                if abs(rnx-rx) + abs(rny-ry) > abs(bnx-bx) + abs(bny-by): 
                    rnx -= dx[i]
                    rny -= dy[i]
                else:
                    bnx -= dx[i]
                    bny -= dy[i]
            
            if (rnx,rny,bnx,bny) not in visited:
                visited.append((rnx,rny,bnx,bny))
                q.append((rnx, rny, bnx, bny))
    cnt += 1
print(-1)

배운점

• visited 역시 graph 처럼 2차원 리스트로 표현 해야한다는 고정관념을 지우자.
• 순회할 때마다 depth를 증가시켜서 depth 값을 통해 return을 하는 경우는 dfs에서만 가능하다고 생각했었는데

for _ in range(len(q)):
	~~
cnt += 1

이런 방식을 통해서도 bfs를 통해서도 depth를 구할수 있다는 점을 알게되었다.