백준 17086번: 아기상어2 Python 풀이 및 정답 코드

문제 링크

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

17086번: 아기 상어 2

 

 

 

문제 설명

문제

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

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

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

입력

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

출력

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

 

 

 

문제 풀이

똑똑하게... 누적합으로 풀어보겠다고 하다가 복잡해져서 관뒀다.
사실 행렬 크기 최대가 50이라 시간 효율성은 아예 똥싸놓지만 않으면 괜찮을 것 같다.

풀이는 별거 없다... 그냥 무식하게 거리가 d인 정사각형 테두리에 있는 녀석들 조사해서 1이면 d를 리턴해줬다.
getMatrix는 좀 특이한데 IndexError 일일이 처리하는게 귀찮아서 아예 get 함수를 따로 만들었다.
인덱스를 벗어나면 무조건 0을 리턴하는 함수이다. 어차피 상어를 찾는거니까 그렇게 해도 문제 없다.

처음에 작성한 코드는 다음과 같다.

N, M = map(int, input().split())
matrix = [list(map(int, list(input().split()))) for _ in range(N)]
m = [[0] * M for _ in range(N)]

answers = []


def getMatrix(i, j):
    try:
        return matrix[i][j]
    except IndexError:
        return 0


def bfs(i, j):
    for d in range(max(i, j, N - i - 1, M - j - 1)):
        for n in range(-d, d + 1):
            if 1 in [
                getMatrix(i - d, j + n),
                getMatrix(i + d, j + n),
                getMatrix(i + n, j - d),
                getMatrix(i + n, j + d),
            ]:
                return d
    return max(i, j, N - i - 1, M - j - 1)


for i in range(N):
    for j in range(M):
        m[i][j] = bfs(i, j)

print(m)

완벽하다고 생각했지만 틀렸다...
왜냐면 쓸데없이 친절한 파이썬은 인덱스에 -1이 들어가도 인덱스 에러를 내지 않고 역순의 첫번째, 즉 마지막 원소를 리턴해버리기 때문이다.

결국 깔끔했던 try except문을 다음과 같이 고쳐 통과 했다.

 

 

 

코드

N, M = map(int, input().split())
matrix = [list(map(int, list(input().split()))) for _ in range(N)]

answers = []

# 인덱스 에러를 핸들링하기 위해 get 함수를 따로 작성
def getMatrix(i, j):
    if i < 0 or j < 0 or i >= N or j >= M:
        return 0
    else:
        return matrix[i][j]


# (i,j)의 안전거리를 bfs로 탐색해서 리턴
def bfs(i, j):
    for d in range(max(N, M)):
        # (i,j)로 부터 거리가 d인 정사각형 테두리의 상어들을 조사한다.
        for n in range(-d, d + 1):
            if 1 in [
                getMatrix(i - d, j + n),
                getMatrix(i + d, j + n),
                getMatrix(i + n, j - d),
                getMatrix(i + n, j + d),
            ]:
                return d


for i in range(N):
    for j in range(M):
        answers.append(bfs(i, j))

print(max(answers))

 

 

 

결과

메모리	시간
30864 KB	1536 ms

 

 

 

다른 사람의 코드

# 파싱
n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]

# 상어 체크
sharks = set()
for i in range(n):
    for j in range(m):
        if maps[i][j] == 1:
            sharks.add((i, j))

# 거리 체크
answer = 0
for i in range(n):
    for j in range(m):
        temp = 50
        for a, b in sharks:
            temp = min(temp, max(abs(i - a), abs(j - b)))
        answer = max(temp, answer)

# 결과 출력
print(answer)

상어가 있는 곳의 위치를 저장하고 상어가 있는 곳 중 가장 가까운 거리를 저장한다.
이러면 시간 효율성은 장담할 수 없지만 정사각형 테두리를 계산하고 인덱스에러를 신경쓰고 할 필요가 없으므로 확실히 코드는 간단해진다.

 

MIS = lambda: map(int,input().split())
from collections import deque

n, m = MIS()
grid = [list(MIS()) for i in range(n)]
Q = deque([(i,j) for i in range(n) for j in range(m) if grid[i][j] == 1])
while Q:
    i, j = Q.popleft()
    for ni,nj in (i-1,j-1),(i-1,j),(i-1,j+1),(i,j-1),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1):
        if not (0<=ni<n and 0<=nj<m) or grid[ni][nj]: continue
        grid[ni][nj] = grid[i][j]+1
        Q.append((ni,nj))
print(max(map(max,grid))-1)

람다? 이해 못함
근데 시간이 나보다 1/20배이다. 
상어가 있는 위치를 q에 넣고 propagation 해주는 방식인 것 같다.
천재같음 진짜 짜증남

 

 

 

리뷰