백준/ Silver 2 문제 , 백준 파이썬 17086 , 아기 상어 2 [BFS]

백준/ Silver 2 문제 , 백준 파이썬 17086 , 아기 상어 2 [BFS]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

문제 출처

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

17086번: 아기 상어 2

 

 

풀이

 

두가지 풀이로 풀었다.

 

첫 번째는 리스트에 1이 적인 위치들을 모두 파악한다음에 동시에 넓혀 나아가는 방법이다.

 

두 번째는 1을 제외한 0의 모든 자리에서 최대한 퍼져 나갈 수 있는 위치를 체크한다.

 

하지만, 모든 0 자리에서 체크를 해야해서 python3 에서는 시간초과가 발생하여 pypy3로만 통과가 가능하다.

 

 

 

정답

 

1. 1위치부터 체크해서 찾기

 

 

 

 

2. 0부터 체크해서 찾기 (pypy3로만 통과)

 

1.

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

vertical=[1,-1,0,0,1,1,-1,-1]
parallel=[0,0,1,-1,-1,1,-1,1]

N,M=map(int,input().split())
MAP=[list(map(int,input().split())) for _ in range(N)]
dq=deque()
for i in range(N):
    for j in range(M):
        if MAP[i][j]==1:
            dq.append([i,j])

def bfs():
    MAX=0
    while dq:
        X,Y=dq.popleft()
        for i in range(8):
            mx,my=X+vertical[i],Y+parallel[i]
            if 0<=mx<N and 0<=my<M:
                if MAP[mx][my]==0:
                    dq.append([mx,my])
                    MAP[mx][my]=MAP[X][Y]+1
                    if MAX<MAP[mx][my]:
                        MAX=MAP[mx][my]
    return MAX-1

print(bfs())

 

2. 

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


vertical=[1,-1,0,0,1,1,-1,-1]
parallel=[0,0,1,-1,-1,1,-1,1]

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

def bfs(x,y):
    dq=deque()
    dq.append([x,y])
    L=deepcopy(MAP)
    cnt=0
    visited=[[False for _ in range(M)] for _ in range(N)]
    visited[x][y]=True
    check=False
    while dq:
        if check==True:
            break
        X,Y=dq.popleft()
        for i in range(8):
            mx,my=X+vertical[i],Y+parallel[i]
            if 0<=mx<N and 0<=my<M:
                if MAP[mx][my]==0 and visited[mx][my]==False:
                    dq.append([mx,my])
                    visited[mx][my]=True
                    L[mx][my]=L[X][Y]+1
                    if cnt<L[mx][my]:
                        cnt=L[mx][my]
                elif MAP[mx][my]==1:
                    cnt=L[X][Y]+1
                    check=True
                    break
    return cnt
    
MAX=0
for i in range(N):
    for j in range(M):
        if MAP[i][j]==0:
            result=bfs(i,j)
            if MAX<result:
                MAX=result

print(MAX)