[백준] 18405 경쟁적 전염[Python]

이 문제는 기본적은 bfs문제에서 살짝 꼬아서 낸 문제입니다. 

 

저는 처음 문제를 읽고 풀 때 N*N 배열을 N*K 배열로 글을 잘 못 읽고 풀어서 indexerror가 많이 발생했었는데 다시 제대로 읽어보니 N*N배열이고 K는 바이러스의 종류라는 것을  깨달았습니다..

 

 bfs,dfs 문제를 풀 때에는 각 행,열의 변수와 문제에서 주어지는 조건 변수들을 잘 정리하고 문제를 풀기 시작하면 도움이 될 것 같습니다.

 

 

    #N,K의 입력을 받음 
    N,K = map(int,s.readline().split())
    
    #각 행을 graph 이중배열에 저장
    graph=[list(map(int,s.readline().split()))for _ in range(N)]
    
    # S,X,Y의 값 입력 받음
    S,X,Y = map(int,s.readline().split())
    
    #바이러스 종류와 위치 저장할 배열 생성
    answer = []* N
    q= deque()
    
    #배열 pop할 때 쓰일 cnt변수 생성
    cnt=0
    
    #방문 표시를 위한 v배열 생성
    v=[[0]*N for _ in range(N)]

 

위의 부분은 문제에 필요한 기본적은 데이터들을 입력하고 필요한 변수, 배열들을 생성해주는 과정입니다. 이 문제는 방문체크를 해서 방문안한 부분들을 위주로 체크를 해야하므로 v배열을 생성했습니다.

 

 

    #반복문을 통해 바이러스의 위치를 찾고 answer배열에 
    #바이러스 값과 위치를 저장하고 방문표시
    for i in range(N):
        for j in range(N):
            if graph[i][j]:
                temp = graph[i][j]
                answer.append((temp,i,j))
                v[i][j]=1
                
    #바이러스를 작은순서부터 pop해야하므로 오름차순정렬
    answer.sort(key=lambda x:x[0])

    #q에 좌표값들을 순서대로 append
    for i in answer:
        q.append((i[1],i[2]))

 

바이러스의 위치를 찾고 바이러스 순서대로 bfs를 실행하는게 이 문제의 핵심이기 때문에 어떻게 찾고 큐에 넣을지가 중요합니다.

위의 방법은 graph의 모든 부분을 탐색하고 바이러스의 값과 위치를 answer 배열에 저장을 합니다. 

그리고 저장된 바이러스를 정렬하고 작은 순서부터 큐에 append해서 바이러스를 작은거 부터 bfs를 실행시킵니다.

 

#bfs 함수부분
def bfs(ci,cj):
    global cnt
    v[ci][cj]=1
    
    while q:
        #pop할때마다 cnt를 1씩 증가시키고
        #그 값이 S*(len(answer))값과 같으면 종료
        if cnt ==S*(len(answer)):
            break
        ci,cj = q.popleft()
        cnt +=1
        
        #방향을 위한 변수 선언
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        
        #우,하,좌,상 순서대로 방문 
        for i in range(4):
            nx = ci+dx[i]
            ny = cj+dy[i]
            
            #범위안에 들어오고 방문안한 대상들을 방문하고 q에 넣어주는거 반복
            if 0<=nx<N and 0<=ny<N and not v[nx][ny]:
                v[nx][ny] = 1
                graph[nx][ny]=graph[ci][cj]
                q.append((nx,ny))

 

bfs 함수부분의 코드입니다. 이 부분에서 중요한 것은 주어진 S를 활용해서 언제 while문을 탈출하느냐인데 S초만큼 반복을해야하는데 이것은 그래프안의 바이러스 개수와 연관이 되어있기 때문에 S*(len(answer))를 사용해서 cnt값이 같아지면 break합니다.

 

아래는 전체코드입니다

from sys import stdin as s
from collections import deque
s = open('input.txt','rt')


#bfs 함수부분
def bfs(ci,cj):
    global cnt
    v[ci][cj]=1
    
    while q:
        #pop할때마다 cnt를 1씩 증가시키고
        #그 값이 S*(len(answer))값과 같으면 종료
        if cnt ==S*(len(answer)):
            break
        ci,cj = q.popleft()
        cnt +=1
        
        #방향을 위한 변수 선언
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        
        #우,하,좌,상 순서대로 방문 
        for i in range(4):
            nx = ci+dx[i]
            ny = cj+dy[i]
            
            #범위안에 들어오고 방문안한 대상들을 방문하고 q에 넣어주는거 반복
            if 0<=nx<N and 0<=ny<N and not v[nx][ny]:
                v[nx][ny] = 1
                graph[nx][ny]=graph[ci][cj]
                q.append((nx,ny))
    

if __name__=='__main__':
    
    #N,K의 입력을 받음 
    N,K = map(int,s.readline().split())
    
    #각 행을 graph 이중배열에 저장
    graph=[list(map(int,s.readline().split()))for _ in range(N)]
    
    # S,X,Y의 값 입력 받음
    S,X,Y = map(int,s.readline().split())
    
    #바이러스 종류와 위치 저장할 배열 생성
    answer = []* N
    q= deque()
    
    #배열 pop할 때 쓰일 cnt변수 생성
    cnt=0
    
    #방문 표시를 위한 v배열 생성
    v=[[0]*N for _ in range(N)]
    

    #반복문을 통해 바이러스의 위치를 찾고 answer배열에 
    #바이러스 값과 위치를 저장하고 방문표시
    for i in range(N):
        for j in range(N):
            if graph[i][j]:
                temp = graph[i][j]
                answer.append((temp,i,j))
                v[i][j]=1
                
    #바이러스를 작은순서부터 pop해야하므로 오름차순정렬
    answer.sort(key=lambda x:x[0])

    #q에 좌표값들을 순서대로 append
    for i in answer:
        q.append((i[1],i[2]))

    #최초 bfs함수호출)
    bfs(answer[0][1],answer[0][2])
    
    #X,Y좌표가 (1,1)부터 시작하므로 1씩빼준 값이 존재하면
    #그 값을 출력하고 없으면 0 출력
    if graph[X-1][Y-1]:
        print(graph[X-1][Y-1])
    else:
        print(0)