[Python] 백준 1103. 게임

 

https://www.acmicpc.net/problem/1103

 

 

풀이

델타탐색 값에다가 탐색할 곳에 있는 숫자만큼 곱해줘서 탐색 영역을 설정하고

조건문을 통해 retire 되는 케이스를 continue로 넘기고

이동 횟수를 갱신해주면서 bfs 탐색을 한다.

탐색했던 자리를 다시 탐색하는 case가 나온다면 무한 루프에 빠진 것이다.

n*m 배열에서 이동횟수가 n*m을 넘어간다는 건 어딘가 2번 이상 방문했다는 의미이므로

-1을 출력하고 종료한다.

 

 

코드

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(input().rstrip()) for _ in range(n)]
visit = [[0]*m for _ in range(n)]
max_val = 1
def bfs():
    global max_val
    q = deque()
    q.append((0,0))
    visit[0][0] = 1
    while q:
        x,y = q.popleft()
        for i in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx = x + (i[0] * int(board[x][y]))
            ny = y + (i[1] * int(board[x][y]))
            # 밖으로 나가거나 구멍에 빠지면
            if nx < 0 or nx >= n or ny < 0 or ny >= m or board[nx][ny] == 'H':
                continue

            if visit[nx][ny] < visit[x][y] + 1:
                q.append((nx,ny))
                visit[nx][ny] = visit[x][y] + 1
                max_val = max(max_val, visit[nx][ny])

            if max_val > n*m:
                print(-1)
                exit()
    return max_val
print(bfs())