코드트리 빵 [삼성 기출]

1. 문제 접근 방법

- 문제를 처음 잘못 접근했던 문제이다.

  편의점으로 가는 최단 거리를, 매 시간마다 새로 구해서 업데이트 해야 한다. 

  이 때, 중간에 변경되는 사항을 고려해줘야 한다 

  변경되는 사항이란, 새로 업데이트되는 편의점, 베이스캠프를 의미한다. 

   이 점을 고려해서 지나가지 못하도록 해야 한다.

   해설 코드를 참고해서 올린다. 

 

2. 코드

from collections import deque 

n, m = map(int, input().split())

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

def isInside(x, y):
    if 0<=x and x < n and 0<=y and y<n:
        return True
    else:
        return False

isArrived = [0]*m
board = [] 
stores = []

for i in range(n):
    row = list(map(int, input().split()))
    board.append(row)
    
    
for i in range(m):
    x, y = map(int, input().split())
    stores.append([x-1, y-1])
    
    
people = []

for i in range(m):
    people.append([-1, -1])

time = 1 
visited = [[False]*n for _ in range(n)]
step = [[0]*n for _ in range(n)]



def bfs(store):

	## visited와 step을 전역으로 사용하고,
    ## bfs를 쓸 때마다, 새로 업데이트해준다는 것이 이 풀이의 핵심이다. 
    for i in range(n):
        for j in range(n):
            visited[i][j] = False
            step[i][j] = 0
            
    
    x = store[0]
    y = store[1]
    
    q = deque()
    q.append([x,y])
    visited[x][y] = True
    step[x][y] = 0 
    
    while q:
    
        x, y = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            ## 이동하면서, step과 visited에 정보를 기록해둔다. 
            if isInside(nx, ny) and visited[nx][ny] == False and board[nx][ny] != 2:
                visited[nx][ny] = True
                step[nx][ny] = step[x][y] + 1 
                q.append([nx, ny])
    




while True:
    
    for i in range(m):
        
        if (people[i][0] == -1 and people[i][1] == -1) or isArrived[i] == 1:
            continue
        
        bfs(stores[i])
        
        x = people[i][0]
        y = people[i][1]
        
        minDist = 1000000
        minX = -1
        minY = -1 
        
        ## 4개의 점 중에서 다음 점이, 
        ## board안에 있으면서,
        ## 방문한 적이 있고(최단 거리는 방문 가능한 점이어야 하므로)
        ## 가장 거리가 짧은 곳을 골라서, 그 점으로 한 칸 이동한다. 
        for j in range(4):
            nx = x + dx[j]
            ny = y + dy[j]
            
            if isInside(nx, ny) and visited[nx][ny] and minDist > step[nx][ny]:
                minDist = step[nx][ny]
                minX = nx
                minY = ny 
                
        ## 이동한 점을 people에 업데이트해준다. 
        people[i][0] = minX
        people[i][1] = minY
        
        ## 사람이 편의점에 도착하면,
        ## 도착했다는 처리를 해준다. 
        if people[i] == store[i]:
            isArrived[i] = 2
        
    
    
    for i in range(m):
        if isArrived[i] == 2:
            isArrived[i] = 1
            x = people[i][0]
            y = people[i][1] 
            board[x][y] = 2 
        
    
    cnt = 0
    
    allArrived = True
    
    ## 이렇게 for문에 break를 걸어주면 
    ## 시간 복잡도를 줄일 수 있다 
    for i in range(m):
        if isArrived[i] == 0:
            allArrived = False
            break
            
    
    if allArrived == True:
        break 
    
    
    if time <= m:
        bfs(stores[time-1])
        
        ## minDist는 임의의 큰 값을 넣는다 
        minDist = 1000000
        minX = -1
        minY = -1
        
        ## bfs에서 편의점을 기준으로 베이스캠프를 탐색을 할 때,
        ## 방문 가능한 베이스캠프이면서, 가장 가까운 베이스캠프를 찾는다
        ## 2중 for문을 저렇게 순회하면, 자동으로 가장 작은 row, col을 찾을 수 있다. 
        for i in range(n):
            for j in range(n):
                if visited[i][j] and board[i][j] == 1 and minDist > step[i][j]:
                    minDist = step[i][j]
                    minX = i
                    minY = j 
        
        
        people[time-1][0] = minX
        people[time-1][1] = minY
        board[minX][minY] = 2 
        
    time += 1 


print(time)