[Python] 17129번 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

✏️ 문제

 

문제 파악

예제의 값은 잘 나왔지만 제출했을 때 시간 초과가 계속 떠서 시간을 많이 잡아먹었었는데 찾아보니 다들 똑같은 이유로 python3 대신 pypy3 로 제출하고 있었다.. python3 로 맞힌 사람은 딱 한 사람뿐... (멋있다..)

 

pypy3 로 제출했더니 틀렸다고 나왔는데 3, 4, 5를 만났을 때 return 하도록 하는 if 조건문의 위치를 잘못두고 있었다...!

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

코드

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

q = deque()
n, m = map(int, input().split())
graph = [list(map(int, list(str(input().rstrip())))) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
start_x, start_y = 0, 0

for i in range(n):
  for j in range(m):
    if graph[i][j] == 2:
      start_x, start_y = i, j

def bfs(x, y):
  q.append([x, y])
  visited[x][y] = 1

  while q:
    x, y = q.popleft()

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

      if 0 <= dx < n and 0 <= dy < m and visited[dx][dy] == 0 and graph[dx][dy] != 1:
        visited[dx][dy] = visited[x][y] + 1
        q.append([dx, dy])

        if graph[dx][dy] in (3, 4, 5):
          return visited[dx][dy] - 1
  
  return -1

res = bfs(start_x, start_y)
if res != -1:
  print("TAK")
  print(res)
else:
  print("NIE")

 

 

 

---

 

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

[알고리즘] DFS와 BFS