[백준] 16173번 점프왕 쩰리(Small)

💡문제접근

• BFS로 탐색을 수행하는 코드로 방향을 잡았는데 문제는 오른쪽 방향, 아래 방향으로만 이동이 가능하다는 것이다.
• 두 가지 경우에 대해서만 BFS를 수행할 수 있도록 BFS 코드를 수정해서 우하향 좌표에 도달할 수 있는지 여부를 체크했다.

💡코드(메모리 : 34184KB, 시간 : 64ms)

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
graph = [list(map(int, input().strip().split())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]


def BFS(a, b):
    queue = deque()
    queue.append([a, b])
    visited[a][b] = True
    while queue:
        y, x = queue.popleft()

        if y == N - 1 and x == N - 1:
            if visited[y][x]:
                return "HaruHaru"
		
        # 영역 밖으로 나가게 되는 경우 게임에서 패배
        if y < 0 or y >= N or x < 0 or x >= N:
            continue
        else:
        	# 아래 방향으로만 이동이 가능한 경우
            if y + graph[y][x] < N and not visited[y + graph[y][x]][x]:
                visited[y + graph[y][x]][x] = True
                queue.append([y + graph[y][x], x])
			
            # 오른쪽 방향으로만 이동이 가능한 경우
            if x + graph[y][x] < N and not visited[y][x + graph[y][x]]:
                visited[y][x + graph[y][x]] = True
                queue.append([y, graph[y][x] + x])
    return "Hing"


result = BFS(0, 0)
print(result)

💡소요시간 : 24m