[파이썬/python] 백준 1795 - 마알

import sys, math
from collections import deque

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

path = []

N, M = map(int, sys.stdin.readline().split())


for i in range(N):
    temp = sys.stdin.readline().rstrip()
    temp_arr = []
    for j, each in enumerate(temp):
        if each == '.':
            temp_arr.append(0)
        else:
            temp_arr.append(int(each))

    path.append(temp_arr)

deq = deque()


def bfs(x, y):
    deq.append((x, y, 0))
    visited = [[1e9 for _ in range(M)] for _ in range(N)]

    while deq:
        x, y, cnt = deq.popleft()

        if visited[x][y] <= cnt:
            continue
        visited[x][y] = cnt

        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < N and 0 <= ny < M:
                deq.append((nx, ny, cnt + 1))

    temp = 0
    for i in range(N):
        for j in range(M):
            if path[i][j] != 0:
                temp += math.ceil(visited[i][j] / path[i][j])
    return temp

ans = 1e9
for i in range(N):
    for j in range(M):
        t = bfs(i, j)
        if t >= 1e8:
            continue
        else:
            ans = min(ans, t)

print(ans) if ans <= 1e8 else print(-1)

BFS 문제입니다.

처음에 카운트마다 체스말들 모두 한번씩 움직이는걸로 잘못 이해해서 시간 날렸습니다..

 

처음 시도로 체스말들을 기준으로 bfs를 실행했으나 메모리 + 시간 초과가 뜨더군요

인터넷에 정보도 없어서 포기하려다가 방법이 생각났습니다.

어차피 최대 10 * 10 사이즈 체스판이기 때문에 모든 칸 기준으로 bfs를 실행하며 각각의 체스말에 도달했을 때 카운트를 더하면 됩니다..

 

1. 모든 체스 칸에 대하여 bfs

2. bfs 진행 중 체스말이 있는 칸이 나오면 저장해둠

3. 저장해둔 카운트들을 모두 더함

4. 결괏값을 리턴하고 리턴값들 중 최솟값이 정답

 

예외처리 하다가 화가 많이 나서 대충했습니다.