코드트리 빵 - python

from collections import deque

dx = [-1,0,0,1]
dy = [0,-1,1,0]
def check_can_move(endXX,endYY,visited):
    if endXX < 0 or endXX >= n or endYY < 0 or endYY >= n or visited[endXX][endYY] == 1 or maps[endXX][endYY] == -1 or maps[endXX][endYY] == -2:
        # 격자 밖 or 이미 들린곳 or 점령된 BC or 점령된 fac
        return False
    return True
def find_route(startX,startY,routeCount,facX,facY):
    for i in range(4):
        visited = [[0 for _ in range(n)] for _ in range(n)]
        visited[startX][startY] = 1
        endX = startX + dx[i]
        endY = startY + dy[i]
        if endX == facX and endY == facY:
            routeCount.append([-1, i])
            break
        if not check_can_move(endX,endY,visited):
            continue
        stack = deque()
        stack.append([endX, endY,0])
        while len(stack) != 0:
            startXX,startYY,tCount = stack.popleft()
            visited[startXX][startYY] = 1
            for j in range(4):
                endXX = startXX+dx[j]
                endYY = startYY+dy[j]
                if not check_can_move(endXX,endYY,visited):
                    continue
                if endXX== facX and endYY == facY: #도달한경우
                    routeCount.append([tCount,i])
                    stack.clear()
                    break
                else:
                    stack.append([endXX,endYY,tCount+1])
def move_all_1():
    for i in range(len(player)):
        startX,startY,facX,facY,m = player[i]
        routeCount = [] #[count,rank]
        find_route(startX,startY,routeCount,facX,facY)
        # print(routeCount)
        routeCount.sort(key=lambda x: (x[0],x[1]))
        short_dir = routeCount[0][1]
        endX = startX+dx[short_dir]
        endY = startY+dy[short_dir]
        player[i][0] = endX
        player[i][1] = endY
def check_end():
    for i in range(len(player)-1,-1,-1):
        if player[i][0] == player[i][2] and player[i][1] == player[i][3]:#편의점 도착
            maps[player[i][0]][player[i][1]] = -2  # 도착한 편의점 못지나감
            player.pop(i)


def go_BC(t):
    facX,facY = fac[t-1]
    stack = deque()
    stack.append([facX,facY])
    visited = [[0 for _ in range(n)] for _ in range(n)]
    while len(stack) != 0:
        # print(stack)
        startX,startY = stack.popleft()
        visited[startX][startY] = 1
        for j in range(4):
            endX = startX+dx[j]
            endY = startY+dy[j]
            if not check_can_move(endX,endY,visited):
                continue
            if maps[endX][endY] == 1 or maps[endX][endY] == -1: #갈 수 있는 곳인데 거기에 BC있으면?
                maps[endX][endY] = -1
                player.append([endX,endY,facX,facY,t-1])
                stack.clear()
                break
            else:
                stack.append([endX,endY])

n,m = map(int,input().split())
maps = []
for _ in range(n):
    maps.append(list(map(int,input().split())))
fac = []
for _ in range(m):
    tempList = list(map(int,input().split()))
    tempList[0] -= 1
    tempList[1] -= 1
    fac.append(tempList)

player = [1]
times = 0
check = True
while len(player) != 0:
    #print(player)
    if times == 0:
        player.clear()
    times+=1
    move_all_1()
    check_end()
    if times <= m:
        go_BC(times)

print(times)

 

문제에서 말한 순서 1,2,3을 순차적으로 따르는것이 이 문제의 주요 포인트인듯 하다.

 

생각할 것들

1. 베이스캠프 찾기 : 매분마다 map이 변할 수 있기 때문에 추가할때의 map상황에서 최소 거리를 찾아야 한다.

2. player 이동 : 매분마다 map이 변할 수 있기 때문에 이동할 때마다 편의점까지의 최소거리를 계산해서 움직여야 한다.

 

이동의 우선순위는 상,좌,우,하 이므로 dx,dy를 이에 맞게 초기화해 사용해야 한다.