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

🔗 문제 링크

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

⏰ 소요된 시간

10분

✨ 수도 코드

너무나도 오랜만에 푸는 알고리즘...
DFS와 BFS 복습하기 좋았던 문제였다.

1. DFS

input = open(0).readline

n = int(input())
area = []
dx, dy = [0, 1], [1, 0]
arrive = False
visited = [[0 for _ in range(n)] for _ in range(n)]

def DFS(x, y, visited):
    global arrive
    if area[x][y] == -1:
        arrive = True
    if visited[x][y] == 0:
        visited[x][y] = 1
        for i in range(2):
            nx, ny = x + area[x][y] * dx[i], y + area[x][y] * dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                DFS(nx, ny, visited)


for i in range(n):
    area.append(list(map(int, input().split())))

DFS(0, 0, visited)
print("HaruHaru") if arrive else print("Hing")

2. BFS

from collections import deque
input = open(0).readline

n = int(input())
area = []
q = deque()

dx, dy = [0, 1], [1, 0]
visited = [[0 for _ in range(n)] for _ in range(n)]  # 방문처리

def BFS(visited):
    while q:
        x, y = q.popleft()

        for i in range(2):
            nx, ny = x + area[x][y] * dx[i], y + area[x][y] * dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if area[nx][ny] == -1:
                    return "HaruHaru"

                if visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
            else:
                continue
    return "Hing"

for i in range(n):
    area.append(list(map(int, input().split())))

q.append((0, 0))
print(BFS(visited))

알고리즘을 다시 열심히 풀어봐야겠다!😅