백준/ Gold 5 문제 , 백준 파이썬 18405 , 경쟁적 전염 [BFS]

백준/ Gold 5 문제 , 백준 파이썬 18405 , 경쟁적 전염 [BFS]

 

 

풀이 시간

 

 

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

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

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

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

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

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

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


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


<덧붙일 말>

 

문제 출처

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

18405번: 경쟁적 전염

 

 

풀이

 

 

1. 기본세팅

 

1. 상하좌우 움직임

 

2. N,K 입력 받기

 

3. N행 N열 visited 선언

 

4. N 행의 MAP 리스트를 입력 받는데 0이외의 숫자들의 숫자와 위치를 tmp 에 저장해둔다.

 

5. 이후 오름차순으로 정렬 후 dq에 담아주고 visited에 방문 표시

 

6. S,A,B 입력받기

 

2. BFS 호출 및 처리

 

작은 숫자들 순서로 퍼트려 나가고 이동한 횟수들을 할당한다.

 

이후 도착 지점인 A,B 에 할당된 숫자들을 확인하여 S 보다 큰지 확인하고 조건에 맞게 출력시켜주면된다.

 

(움직일때 1부터 커지기 시작했으므로 S+1 과 비교해줘야 한다.)

 

 

 

 

 

 

정답

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

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

N,K=map(int,input().split())
MAP=[]
tmp=[]
visited=[[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    L=list(map(int,input().split()))
    for j in range(N):
        if L[j]!=0:
            tmp.append([L[j],i,j])
    MAP.append(L)
tmp.sort(key=lambda x:x[0])
dq=deque()
for k in range(len(tmp)):
    dq.append([tmp[k][0],tmp[k][1],tmp[k][2]])
    visited[tmp[k][1]][tmp[k][2]]=1
    
S,A,B=map(int,input().split())
while dq:
    Z,X,Y=dq.popleft()
    for a,b in dr:
        mx,my=X+a,Y+b
        if 0<=mx<N and 0<=my<N:
            if MAP[mx][my]==0:
                MAP[mx][my]=Z
                visited[mx][my]=visited[X][Y]+1
                dq.append([Z,mx,my])

if visited[A-1][B-1]>S+1:
    print(0)
else:
    print(MAP[A-1][B-1])