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

✏️ 문제

 

문제 파악

문제를 읽어봤을 때 방향이 정해졌을 시 그 방향으로 칸에 적혀있는 수만큼 움직일 수 있는 것 같았다. 

그래서 다음과 같이 코드를 짰다.

다음 x위치 = 현재 x위치 + (움직일 방향 * 현재 밟고 있는 칸에 쓰여 있는 수)
다음 y위치 = 현재 y위치 + (움직일 방향 * 현재 밟고 있는 칸에 쓰여 있는 수)

 

 

다음 x, y 위치가 -1일 경우 1을 리턴하고 끝까지 만나지 못할 경우 0을 리턴하여 이 리턴값을 기준으로 출력하는 문자열을 달리하였다.

 

알고리즘

• 구현
• 브루트포스 알고리즘
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
graph = [[0] * n for _ in range(n)]
visited = [[False] * n for _ in range(n)]
d = [(0, 1), (1, 0)]

for i in range(n):
  line = list(map(int, input().split()))
  for j in range(n):
    graph[i][j] = line[j]

def bfs(x, y):
  q = deque([(x, y)])
  visited[x][y] = True
  
  while q:
    x, y = q.popleft() 

    for i in range(2):
      dx = x + (d[i][0] * graph[x][y])
      dy = y + (d[i][1] * graph[x][y])

      if 0 <= dx < n and 0 <= dy < n and not visited[dx][dy]:
        if graph[dx][dy] == -1:
          return 1

        q.append([dx, dy])
        visited[x][y] = True
  return 0
        
print('HaruHaru' if bfs(0, 0) == 1 else 'Hing')

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS