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

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

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

문제 제목이 너무 충격적이라 정리하고 싶어서 정리..

 

문제

• 딱따구리 위치(2)에서 가장 가까운 음식 (3, 4, 5)까지의 거리를 구하는 문제

풀이

1. 딱따구리 위치를 시작점으로 두고 bfs탐색. 거리 저장용 dist, 방문 여부 확인용 visited배열 2개를 생성.
2. bfs함수 안에서는 dist값 갱신해줌 (이전 값 + 1).
3. 그리고서 탐색하는 중에 3, 4, 5를 만나면 뭐가 됐든 일단 2와 가장 가깝다는 뜻이기 때문에 해당 위치의 거리를 리턴하고 함수를 종료.
   => 3번 같이 한 이유 : 원래는 탐색을 다 돌고 3, 4, 5가 있는 위치까지의 거리를 dist에서 구하고, 최소값을 구했는데요, 메모리 초과 발생. 그래서 bfs를 끝까지 탐색해서 그런가 싶어서 3번 같이 바꿨고 메모리 초과가 없어짐~ 

코드

import sys
from collections import deque

input = sys.stdin.readline

# n 행 세로, m 열 가로 입력
n, m = map(int, input().split())

# 보드 만들고
board = [[0] * m for _ in range(n)]

# 입력받음 (시작위치인 2위치 기억해둠)
# 3, 4, 5 위치 저장해놓기 딕셔너리에 => 제거
for i in range(n):
    temp = input().rstrip()
    for j in range(m):
        if temp[j] == '2':
            start = (i, j)
        board[i][j] = int(temp[j])

# dist, visited 생성 (각 각 거리, 방문여부 저장)
dist = [[-1] * m for _ in range(n)]
visitied = [[False] * m for _ in range(n)]

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

# 시작위치에서 bfs호출
# 0이면 못지나감
def bfs(y, x):
    dq = deque()
    dq.append((y, x))
    dist[y][x] = 0

    while dq:
        cur_y, cur_x = dq.popleft()

        for i in range(4):
            ny = cur_y + dy[i]
            nx = cur_x + dx[i]

            # 범위 벗어나거나 1로 막혀있거나 이미 방문했으면 continue
            if ny < 0 or ny >= n or nx < 0 or nx >= m: continue
            if board[ny][nx] == 1: continue
            if visitied[ny][nx]: continue

            visitied[ny][nx] = True
            dist[ny][nx] = dist[cur_y][cur_x] + 1

            # 현재 위치가 3, 4, 5 중 하나이면 거리를 리턴
            if board[ny][nx] in [3, 4, 5]:
                return dist[ny][nx]

            dq.append((ny, nx))


answer = bfs(start[0], start[1])

if answer is not None:
    print('TAK')
    print(answer)
else:
    print('NIE')