[백준(BOJ)] 17129번 : 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 - PYTHON[파이썬]

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

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

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

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

 

---

 

⊙ 문제 접근 과정

 

윌리암슨수액빨이딱따구리 식구는 식사를 하고 싶어 하는데 귀찮아서 가장 가까운 곳을 가고 싶어 하는 간단한 문제다.

 

1은 벽, 0은 통로이고 윌리암슨수액빨이딱따구리 식구는 2번이다.

 

3, 4, 5는 각각 청국장, 스시, 맥 앤 치즈인데 아무튼 3, 4, 5로 가면 된다.

 

bfs를 돌려서 가장 가까운 음식점까지의 거리 출력!!

 

---

 

⊙ 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
arr = [list(map(int, input().strip())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
q = deque()
dx = [0,0,-1,1]
dy = [1,-1,0,0]

def bfs(x,y):
    global ans
    q.append([x,y])
    visited[x][y]+=1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M and arr[nx][ny] != 1 and not visited[nx][ny]:
                    q.append([nx,ny])
                    visited[nx][ny]= visited[x][y] +1
                    if arr[nx][ny] in (3,4,5):
                        print('TAK')
                        print(visited[x][y])
                        exit()
    print('NIE')

for i in range(N):
    for j in range(M):
        if arr[i][j]==2:
            bfs(i,j)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!