[백준] 17086 아기 상어2 - 파이썬

문제

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

17086번: 아기 상어 2

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자. 

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다.

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

 

 

---

풀이

 

세상에 이렇게 멍청할 수가..

문제를 잘못 봐서 삼십 분 동안 첫 번째 예시 출력값을 이해 못했다.

상어와 상어와의 거리 중 가장 큰 값을 출력하라는 것으로 이해했다.

상어와 가장 멀리 떨어진 칸까지의 거리를 출력하는 문제였다.

내가 비문학을 이렇게 못했나.. 책 좀 읽어야겠다.

 

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

INF = 51
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF]*m for _ in range(n)]

dir = [(1, -1), (-1, 1), (1, 0), (0, 1), (1, 1), (-1, -1), (-1, 0), (0, -1)]

def bfs(r, c):
    q = deque([(r, c)])

    while q:
        i, j = q.popleft()

        for d in dir:
            if not ((0 <= i+d[0] < n) and (0 <= j+d[1] < m)): #보드 밖으로 나가지 않게
                continue
            if dist[i+d[0]][j+d[1]] > dist[i][j] + 1:
                dist[i+d[0]][j+d[1]] = dist[i][j]+1
                q.append((i+d[0], j+d[1]))

for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            dist[i][j] = 0
            bfs(i, j)

print(*dist, sep="\n")
print(max(max(dist)))

정신 차리고 다시 풀었는데 채점 뜨자 마자 틀렸습니다 나온다 ㅠ

내가 넣은 예시는 다 제대로 출력되어서 반례 찾아달라고 게시글 올렸다..

 

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

n, m = map(int, input().split())
dist = [list(map(int, input().split())) for _ in range(n)]

dir = [(1, -1), (-1, 1), (1, 0), (0, 1), (1, 1), (-1, -1), (-1, 0), (0, -1)]
q = deque([])

def bfs():
    while q:
        i, j = q.popleft()

        for d in dir:
            if not ((0 <= i+d[0] < n) and (0 <= j+d[1] < m)): #보드 밖으로 나가지 않게
                continue
            if not dist[i+d[0]][j+d[1]]:
                dist[i+d[0]][j+d[1]] = dist[i][j]+1
                q.append((i+d[0], j+d[1]))

for i in range(n):
    for j in range(m):
        if dist[i][j] == 1:
            q.append((i, j))

bfs()
print(max(max(dist))-1)

내 코드에서 다른 분 코드 참고해서 좀 바꿔봤다.

이 분 코드가 맞다는 것은 알겠는데 내 코드가 왜 틀렸는지 모르겠다. ㅜ

 

 

+) 문제 찾았다

막줄에 print(max(max(dist)))가 틀렸었다..

print(max(map(max, dist)))로 바꿔주니 맞았다.

 

이중 배열에 max를 취하면 리스트 원소 합이 가장 큰 배열이 나온다고 한다.

나는 각 row에서 max값만 모아놓은 list가 나오는 줄 알고 저렇게 썼었다.

한시간 삽질한듯 ^^,,