[백준] 16173 - 점프왕 쩰리 (python 파이썬)

백준 16173 문제 바로가기

풀이 코드

from collections import deque

n = int(input())  # 구역의 크기
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [1, 0]  # 아래, 오른쪽으로 움직였을때의 방향
dy = [0, 1]
visited = [[0] * n for _ in range(n)]
bfs_visited = [[0] * n for _ in range(n)]


# def dfs(x, y):
#     if x >= n or x <= -1 or y >= n or y <= -1:  # 범위를 벗어나지 않도록
#         return False
#     if visited[x][y] == 1:
#         return False
#
#     if graph[x][y] == -1:
#         print('HaruHaru')
#         exit()  # 종료
#
#     visited[x][y] = 1
#
#     for i in range(2):
#         nx = x + dx[i] * graph[x][y]
#         ny = y + dy[i] * graph[x][y]
#         dfs(nx, ny)
#     return True


def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    bfs_visited[x][y] = 1
    while queue:
        x, y = queue.popleft()
        for d in range(2):
            nx = x + dx[d] * graph[x][y]
            ny = y + dy[d] * graph[x][y]
            if nx < n and ny < n and bfs_visited[nx][ny] == 0:
                bfs_visited[nx][ny] = 1
                queue.append((nx, ny))
    return bfs_visited[n - 1][n - 1]


# if dfs(0, 0):
#     print('Hing')

if bfs(0, 0) == 1:
    print('HaruHaru')
else:
    print('Hing')

DFS로 탐색을 하면서 정사각형 구역 내의 수가 -1인 순간에 HaruHaru를 출력하고 exit()함수로 종료하도록 구현했다.
빠져나오지 않고 그대로 DFS함수를 실행하면서 True가 반환되면 도달해야하는 목적지로 가지 못한걸로 판단되어 Hing을 출력하도록 했다.

----bfs추가----
bfs로도 풀 수 있어서 코드를 추가해봤다.
deque모듈을 사용해 queue에 시작점 0,0을 넣어주고 방문했는지 판별하기 위한 bfs_visited에는 1로 값을 바꿔준다.
queue가 모두 비어질때까지 반복한 후 마지막 인덱스 값이므로 -1을 해주어서 return받은 후 그 값이 1이라면 HaruHaru를 출력, 아니라면 Hing을 출력

TODO

BFS로도 풀 수 있는 문제이기 때문에 추가로 BFS로 문제를 풀어서 수정 예정!!