BFS,DFS

• ‘bfs와 dfs중 하나를 선택하여 -1의 값을 가진 타일에 도달하는 것’이 목표였던 문제
  - dfs는 하나의 노드의 자식들에 관한 모든 경우에 수를 다 탐색을 하기 때문에 좀 느릴 것 같아 bfs로 접근함
  
  
  
  

어려웠던 점

• dx,dy의 개념을 생각하지 못 했었음.

• 그래프를 탐색하기 위해 해당 index의 값을 나타내는 좋은 방법인 것 같다.

  • 방향 벡터의 개념으로 생각하면 좀 더 접근하기 쉬운 것 같다.

• 처음 문제를 풀었을 때 bfs에 무조건 노드만 넣어야 겠다는 생각이 강했어서 강박적으로 그래프를 만들고 인접 리스트, 인접 배열을 생성하려고 했었는데, 간단하게 생각하면 더 좋았을 것 같음
  
  
  
  

코드

from collections import deque
import sys

input = sys.stdin.readline

n = int(input().rstrip())

gameZone = []
visited = [[0] * n for _ in range(n)]

for _ in range(n):
    gameZone.append(list(map(int,input().rstrip().split())))

# bfs를 이용하여 탐색
def bfs(gameZone,visited):
    #x방향, y방향 벡터
    dx=[0,1]
    dy=[1,0]

    q = deque()
    q.append((0,0))
    visited[0][0] = 1

    #큐는 집어 넣을 때 방문 처리
    while q:
        curY,curX = q.popleft()

        #종료 조건
        if gameZone[curY][curX] == -1:
            return "HaruHaru"
        
        #오른쪽,아래방향 q에 넣어야함, (dx,dy를 세로로 봐서 아래방향과 오른쪽 방향으로 이동)
        for i in range(2):
            nextY = curY + gameZone[curY][curX] * dy[i]
            nextX = curX + gameZone[curY][curX] * dx[i]
            
            if 0 <= nextX < n and 0 <= nextY < n and visited[nextY][nextX] == 0:
                visited[nextY][nextX] = 1
                q.append((nextY,nextX))

    return "Hing"

print(bfs(gameZone,visited))