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

[문제]

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

16173번: 점프왕 쩰리 (Small)

[풀이]

간단한 dfs 문제였는데 exit(0)을 생각을 못해서 좀 걸렸다

우선 이렇게 풀어놓았지만 exit 을 이용하지 않고 제대로 푸는 방법을 생각해봐야겠다 -> 수정 완료

[코드]

import sys

n = int(sys.stdin.readline())
square = []
for _ in range(n):
    square.append(list(map(int, sys.stdin.readline().split())))
visited = [[False] * n for _ in range(n)]

def dfs(x, y):
    if x >= n or y >= n:
        return False

    value = square[x][y]
    if value == -1:
        print("HaruHaru")
        exit(0)

    if not visited[x][y]:
        visited[x][y] = True
        dfs(x + value, y)  # 아래
        dfs(x, y + value)  # 오른쪽

dfs(0, 0)
print("Hing")

 

[개선된 코드]

import sys
from collections import deque


def solution(N, graph):
    visited = [[False] * N for _ in range(N)]

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

    def dfs(x, y, visited):
        queue = deque()
        queue.append((x, y))

        while queue:
            x, y = queue.popleft()
            if graph[x][y] == -1:
                return 'HaruHaru'

            jump = graph[x][y]  # 점프 값
            for i in range(2):
                nx = x + dx[i] * jump
                ny = y + dy[i] * jump

                if nx >= N or ny >= N:
                    continue
                if visited[nx][ny]:
                    continue
                else:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
        return 'Hing'

    print(dfs(0, 0, visited))


if __name__ == "__main__":
    N = int(sys.stdin.readline())
    graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    solution(N, graph)