[Boj/백준] 17129 Python

문제출처: https://www.acmicpc.net/problem/17129

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

 

 

1. 문제 접근 방식

2를 찾아서 BFS를 시작하고 한칸 움직일때마다 전 칸의 +1을 해준다.

이때 만약 3 4 5 를 만나게되고 visited가 False이면 함수를 종료한다.

 

 

2. 내가 푼 코드

import sys
from collections import deque

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

result = 0

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

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx < 0 or ny < 0 or nx>=n or ny>=m:
                continue
            if visited[nx][ny] == False and (graph[nx][ny] == 3 or graph[nx][ny] == 4 or graph[nx][ny] == 5):
                result = graph[x][y] + 1
                return result
            if graph[nx][ny] != 1 and visited[nx][ny] == False:
                visited[nx][ny] = True
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))
    return 0

n, m = map(int,sys.stdin.readline().split())

graph = []
visited = [[False]*m for _ in range(n)]

for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().strip())))

flag = True

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            k = (bfs(i,j,visited,result))
            flag = False
            break
    if flag == False:
        break

if k:
    print("TAK")
    print(k)
else:
    print("NIE")

 

 

3. 결과 및 느낀점

코드가 많이 난잡하다,,

카운트 값을 하나씩 늘려가면서 BFS를 할때는 값이 겹칠 수 있으므로 visit배열을 사용하도록 하자.

파이썬으로 돌리면 시간초과가 나는데 이 문제를 pypy를 쓰지 않고 맞춘 사람은 없더라,,