[코드트리] 코드트리 빵 - Python

문제 링크

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description?page=1&pageSize=20 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

풀이 

계속 98%에서 틀렸습니다라고 떴는데, 그 이유는 

격자 안 사람들 모두 편의점으로 한 칸 이동 -> 베이스 캠프로 이동 -> 도착한 베이스 캠프 & 편의점 지나갈 수 없음  

해서 그런 것이었다. 

 

문제의 조건을 만족 시키려면 아래와 같이 진행되어야 한다.

격자 안 사람들 모두 편의점으로 한 칸 이동 -> 도착한 편의점 지나갈 수 없음 -> 베이스 캠프로 이동 -> 도착한 베이스 캠프 지나갈 수 없음 

 

1. 편의점으로 한 칸 이동 함수 

우선 순위는 dx와 dy의 순서로 처리가 되므로 따로 체크해줄 필요가 없다. 

현재 위치에서 가고싶은 편의점까지의 최단거리로 한칸 이동시켜준다. 

def find_store(num):
    now_x, now_y = people[num]
    s_x, s_y = want[num]
    
    q = deque()
    # 현재 위치와 지나온 경로 저장 
    q.append((now_x,now_y,[]))
    visited = [ [False] * n for _ in range(n)]
    visited[now_x][now_y] = True 
    result = []
    
    while q:
        x, y, route = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= n :
                continue 
            
            # 도착한 베이스 캠프거나 편의점이면 지나갈 수 없음 
            if graph[nx][ny] == -1:
                continue 
            
            if not visited[nx][ny] :
                tmp = copy.deepcopy(route)
                tmp.append(i)
                visited[nx][ny] = True
                q.append((nx,ny,tmp)) 
                
                # 편의점에 도착했으면 지나온 경로 저장 
                if nx == s_x and ny == s_y:
                    result.append((len(tmp), tmp))
    
    # 최단 거리, 우선 순위로 정렬 
    result.sort()

	# 한 칸 이동 
    return now_x + dx[result[0][1][0]], now_y + dy[result[0][1][0]]

 

2. 베이스 캠프 이동 함수 

가고싶은 편의점에서 가장 가까운 베이스 캠프로 이동시켜준다. 

def find_base(x,y):
    q = deque()
    q.append((x,y,0))
    base = []
    
    visited = [ [False] * n for _ in range(n)]
    visited[x][y] = True 
    
    while q :
        x, y, cnt= q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= n :
                continue 
            
            if graph[nx][ny] == -1:
                continue 
            
            if not visited[nx][ny] :
            	# 베이스 캠프면, 걸리는 시간과 행,열 저장 
                if graph[nx][ny] == 1 :
                    base.append((cnt+1, nx, ny))
                
                visited[nx][ny] = True 
                q.append((nx,ny,cnt+1))
    
    # 시간, 행, 열 순으로 정렬 
    base.sort()
	
    # 이동 
    return base[0][1], base[0][2]

3. 메인 루프 

check 배열에 지나갈 수 없게 되는 편의점 위치를 저장해두었다가 격자 안의 사람들이 다 이동한 후에 지나갈 수 없게 표시해주었다. 

while True :
	# 이동할 수 없게 될 위치 저장  
    check = [] 
    cnt = 0 
    for i in range(1,min(t,m+1)): 
    	# 아직 편의점 도착하지 않은 사람들만 이동 
        if not done[i]:
        	# 편의점으로 한 칸 이동 
            x, y= find_store(i)
            people[i] = [x,y]
            # 편의점 도착했으면 
            if x == want[i][0] and y == want[i][1]:
            	# 지나갈 수 없음 
                check.append((x,y))
                # 도착 완료 표시 
                done[i] = True 
                cnt += 1 
        else :
            cnt += 1 
    
    # 모든 사람이 다 편의점 도착했으면 종료 
    if cnt == m :
        break 
    
    # 격자 안의 사람들이 다 지나가고 난 후이므로, 지나갈 수 없게 표시 
    for a,b in check :
        graph[a][b] = -1 
    
    check = []
    # 베이스 캠프 이동 
    if t <= m :
        x,y = find_base(want[t][0], want[t][1])
        people[t] = [x,y]
        # 지나갈 수 없음 
        graph[x][y] = -1 

    t += 1

 

전체 코드는 아래와 같다.

from collections import deque 
import copy 

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

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

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))
    
def find_base(x,y):
    q = deque()
    q.append((x,y,0))
    base = []
    
    visited = [ [False] * n for _ in range(n)]
    visited[x][y] = True 
    
    while q :
        x, y, cnt= q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= n :
                continue 
            
            if graph[nx][ny] == -1:
                continue 
            
            if not visited[nx][ny] :
                if graph[nx][ny] == 1 :
                    base.append((cnt+1, nx, ny))
                
                visited[nx][ny] = True 
                q.append((nx,ny,cnt+1))
        
    base.sort()

    return base[0][1], base[0][2]

def find_store(num):
    now_x, now_y = people[num]
    s_x, s_y = want[num]
    
    q = deque()
    q.append((now_x,now_y,[]))
    visited = [ [False] * n for _ in range(n)]
    visited[now_x][now_y] = True 
    result = []
    
    while q:
        x, y, route = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= n :
                continue 
            
            if graph[nx][ny] == -1:
                continue 
            
            if not visited[nx][ny] :
                tmp = copy.deepcopy(route)
                tmp.append(i)
                visited[nx][ny] = True
                q.append((nx,ny,tmp)) 
                
                if nx == s_x and ny == s_y:
                    result.append((len(tmp), tmp))
                    
    result.sort()

    return now_x + dx[result[0][1][0]], now_y + dy[result[0][1][0]]

people = [[] for _ in range(m+1)]
want = [[] for _ in range(m+1)] 

for i in range(1,m+1):
    a,b = map(int,input().split())
    want[i] = [a-1,b-1]

t = 1 
done= [False] * (m+1)
while True :
    check = [] 
    cnt = 0 
    for i in range(1,min(t,m+1)): 
        if not done[i]:
            x, y= find_store(i)
            people[i] = [x,y]
            if x == want[i][0] and y == want[i][1]:
                check.append((x,y))
                done[i] = True 
                cnt += 1 
        else :
            cnt += 1 
    
    if cnt == m :
        break 
    
    for a,b in check :
        graph[a][b] = -1 
    
    if t <= m :
        x,y = find_base(want[t][0], want[t][1])
        people[t] = [x,y]
        graph[x][y] = -1 
    t += 1 
print(t)