DFS/BFS: 백준 16173 파이썬

문제:

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

16173번: 점프왕 쩰리 (Small)

 

풀이:

1. DFS

n = int(input())

array = []
for i in range(n):
    array.append(list(map(int, input().split())))

visited = []
for _ in range(n):
    visited.append([False] * n)

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

def dfs(x, y, visited):
    if x >= n or x <= -1 or y >= n or y <= -1:
        return 0
    if visited[x][y] == True:
        return 0
    if array[x][y] == -1:
        print('HaruHaru')
        exit()
    visited[x][y] = True
    for i in range(2):
        nx = x + dx[i] * array[x][y]
        ny = y + dy[i] * array[x][y]
        dfs(nx, ny, visited)
    return True


if dfs(0, 0, visited) == True:
    print('Hing')

 

2. BFS

from collections import deque

n = int(input())

array = []
for _ in range(n):
    array.append(list(map(int, input().split())))

visited = []
for _ in range(n):
    visited.append([False]*n)

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


def bfs(x, y, visited):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    while queue:
        x, y = queue.popleft()
        if array[x][y] == -1:
            return 'HaruHaru'
        for i in range(2):
            nx = x + dx[i] * array[x][y]
            ny = y + dy[i] * array[x][y]

            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if visited[nx][ny] == True:
                continue
            if visited[nx][ny] == False:
                visited[nx][ny] = True
                queue.append((nx, ny))
    return 'Hing'


print(bfs(0, 0, visited))

 

반성:

이번 문제를 풀면서 반성할 부분은 문제를 정확하게 이해하지 못했다는 점이다. 처음에 풀 때는 쪨리가 바로 구역을 

건너뛰는 것이 아니라 한 칸 한 칸 건너가는 것이라고 생각하고 문제를 풀었었는데 결국 해결하지 못해 구글링을 했다. 구글링 해본 결과 쩰리는 점프를 바로 해당 칸으로 하는 것이었고 아이디어를 얻어 문제를 해결할 수 있었다.