2022하_코드트리 빵

문제

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

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

해설(v2 기준)

1. 초기 설정
   1. 베이스 캠프 맵과 사람 맵을 따로 만든다.
   2. 사람 편의점 도착 여부, 사람별 목표 편의점 위치 배열을 각각 선언한다
   3. 탐색 방향은 상,하,좌,우로 한다. 최단거리로 움직이며 최단 거리로 움직이는 방법이 여러가지라면 ↑, ←, →, ↓ 의 우선 순위로 움직이는 조건을 만족한다.
2. 전체 프로세스
   1. 시간은 1초씩 늘어난다.
   2. 편의점 향해 이동
   3. 편의점 모두 도착 여부 체크
   4. 베이스캠프 입장
3. 개별 함수 설명
   1. 편의점 향해 이동
      1. 참가자 이동 예정 위치 리스트와 목표 편의점에 도착한 사람들 정보 리스트를 선언한다.
      2. 격자 내 참가자 존재 위치를 찾고, 참가자별로 위치하는 칸에서 현재 칸~목표한 편의점까지의 최단 루트를 bfs로 찾는다.
         1. 최단 루트는 참가자의 현재 칸~목표한 편의점 위치 까지로 정렬되어 있고, index 1번 요소가 다음에 이동할 칸이다.
      3. 만약 다음 칸이
         1. 목표한 편의점 위치일 경우, 도착한 사람들 정보 리스트에 다음 칸의 위치와 해당 사람의 no를 저장한다.
         2. 그렇지 않을 경우, 참가자 이동 예정 위치 리스트에 참가자의 no를 삽입한다.
      4. 도착한 사람들 정보 리스트를 finish 함수에서 도착 처리한다. 이는 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어지는 조건을 만족하기 위함이다.
   2. 베이스캠프 입장
      1. 현재 시간이 time분이고 time ≤ m를 만족한다면, 해당 time 과 같은 no를 가진 사람을 사람 맵에 넣는다.
      2. 해당 사람의 목표 편의점이 시작 지점이고,
      3. 목표 편의점에서 가장 가까이 위치한 베이스캠프가 도착지점이다.
         1. 이 도착지점을 bfs로 탐색하여 찾는다.
         2. 탐색 도중 발견하는 베이스캠프들의 정보(거리, 행, 열)를 베이스캠프 후보 정보 리스트에 넣는다.
         3. 이를 오름차순 정렬하고 행, 열 정보만 반환한다.
      4. 해당 베이스캠프를 막고, 사람 맵에 해당 사람의 no를 추가한다.

소스코드

v2(2024/04/05)

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

n,m=map(int,input().split())
a=[[[] for _ in range(n)] for _ in range(n)]
b=[list(map(int,input().split())) for _ in range(n)] #  베이스 캠프 맵.(0=빈 공간, 1=베이스캠프, -1=막힌 칸)
arrive=[False]*(m+1) # 사람 편의점 도착 여부
goal=[None]*(m+1) # 사람별 목표 편의점 위치
for no in range(1,m+1):
    x,y=map(int,input().split())
    x-=1
    y-=1
    goal[no]=(x,y)

#   상,좌,우,하
dx=[-1,0,0,1]
dy=[0,-1,1,0]

def inBoard(nx,ny):
    if 0<=nx<n and 0<=ny<n:
        return True
    return False

def bfs1(no,sx,sy):
    ex,ey=goal[no] # 목표 편의점 위치
    q=deque()
    q.append((sx,sy))
    visit=[[False]*n for _ in range(n)]
    visit[sx][sy]=True
    parent=dict() # (다음칸)=(현재칸)

    while q:
        x,y=q.popleft()
        for k in range(4):
            nx,ny=x+dx[k],y+dy[k]
            if inBoard(nx,ny) and not visit[nx][ny] and b[nx][ny]!=-1:
                visit[nx][ny]=True
                q.append((nx,ny))
                parent[(nx,ny)]=(x,y)

    end=(ex,ey)
    start=(sx,sy) # 사람의 현재 위치
    current=end
    route=[current] # 최단 루트
    while current!=start:
        current=parent[current]
        route.append(current)
    route.reverse() #

    return route[1]

# 만약 편의점에 도착한다면 해당 편의점에서 멈추게 되고,
# 이때부터 다른 사람들은 해당 편의점이 있는 칸을 지나갈 수 없게 됩니다.
# 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.
def finish(arrived):
    global b,arrive

    for x,y,no in arrived: # 편의점 도착한 사람들은 해당 칸 지나갈 수 없고, ㄷ착 정보 True로 변경
        b[x][y] = -1
        arrive[no] = True

# 격자에 있는 사람들 모두가 본인이 가고 싶은 편의점 방향을 향해서 1 칸 움직입니다.
# 최단거리로 움직이며 최단 거리로 움직이는 방법이 여러가지라면 ↑, ←, →, ↓ 의 우선 순위로 움직이게 됩니다.
# 여기서 최단거리라 함은 상하좌우 인접한 칸 중 이동가능한 칸으로만 이동하여 도달하기까지 거쳐야 하는 칸의 수가 최소가 되는 거리를 뜻합니다.
def move():
    global a

    arrived=[] # 도착한 사람들 정보 리스트
    tmp=[[[] for _ in range(n)] for _ in range(n)] # 사람 동시 이동할 맵
    for x in range(n):
        for y in range(n):
            if len(a[x][y])>0: # 해당 칸에 사람이 있다면
                for no in a[x][y]: # 사람별로
                    nx,ny=bfs1(no,x,y) # 다음 칸
                    if (nx,ny)==goal[no]: # 목표한 편의점 도착
                        arrived.append([nx,ny,no]) # 도착한 사람들 정보 리스트에 정보 삽입
                        # b[nx][ny]=-1
                        # arrive[no]=True
                    else:
                        tmp[nx][ny].append(no) # 동시 이동할 맵에 표시
    finish(arrived)
    a=tmp

def check():
    for i in range(1,m+1):
        if arrive[i] is False:
            return False
    return True

# 여기서 가장 가까이에 있다는 뜻 역시 1에서와 같이 최단거리에 해당하는 곳을 의미합니다.
# 가장 가까운 베이스캠프가 여러 가지인 경우에는 그 중 행이 작은 베이스캠프, 행이 같다면 열이 작은 베이스 캠프로 들어갑니다.
def bfs2(sx,sy):

    q=deque()
    q.append((sx,sy))
    d=[[-1]*n for _ in range(n)]
    d[sx][sy]=0
    cand=[] # 베이스 캠프 후보 정보 리스트

    while q:
        x,y=q.popleft()
        for k in range(4):
            nx,ny=x+dx[k],y+dy[k]
            if inBoard(nx,ny) and d[nx][ny]==-1 and b[nx][ny]!=-1:
                q.append((nx,ny))
                d[nx][ny]=d[x][y]+1
                if b[nx][ny]==1: # 베이스 캠프 발견했으면
                    cand.append([d[nx][ny],nx,ny]) # 후보 리스트에 정보 삽입

    cand.sort() # 거리,행,열 오름차순 정렬
    return [cand[0][1],cand[0][2]] # 행,열만 반환

# 현재 시간이 t분이고 t ≤ m를 만족한다면,
# t번 사람은 자신이 가고 싶은 편의점과 가장 가까이 있는 베이스 캠프에 들어갑니다.
# t번 사람이 베이스 캠프로 이동하는 데에는 시간이 전혀 소요되지 않습니다.
def enter(time):
    global a,b

    if time<=m:
        sx,sy=goal[time] # 시작지점 : 해당 사람의 목표 편의점
        ex,ey=bfs2(sx,sy) # 도착지점 : 목표 편의점에서 가장 가까이 위치한 베이스캠프
        b[ex][ey]=-1 # 해당 베이스 캠프 막힘
        a[ex][ey].append(time) # 사람 맵에 추가

time=0
while True:
    time+=1
    # 편의점 향해 이동
    move()
    # 편의점 모두 도착 여부
    if check():
        break
    # 베이스캠프 입장
    enter(time)

print(time)

v1(2023/03/29)

import sys
from collections import deque

input=sys.stdin.readline

class Player: # 플레이어 클래스
    def __init__(self,no,ex,ey,x=-1,y=-1): # 초기에는 격자 밖으로 위치 설정(x=-1,y=-1)
        self.no=no
        self.x=x
        self.y=y
        self.ex=ex
        self.ey=ey

n,m=map(int,input().split())
pvisit=[True]+[False]*m # 플레이어 도착 상태 배열
t=1 # 현재 시간
players=[None] # 플레이어 클래스 객체 배열
a=[list(map(int,input().split())) for _ in range(n)] # 맵. 편의점 + 베이스캠프. (0:빈 공간, 1:베이스캠프, 2:편의점, 3:출입금지)

for no in range(1,m+1):
    ex,ey=map(int,input().split())
    ex-=1
    ey-=1
    p=Player(no,ex,ey)
    players.append(p)
    a[ex][ey]=2

#  상,좌,우,하
dx=[-1,0,0,1]
dy=[0,-1,1,0]

# 용도 : 플레이어 현 위치 -> 편의점. 최단 경로
# input : 플레이어 현 위치, 향하는 편의점 위치
# output : 다음 좌표
def bfs1(x,y,ex,ey):
    global a
    # 경로 딕셔너리
    parent=dict()
    q=deque()
    start = [x, y]
    q.append(start)
    d=[[-1]*n for _ in range(n)]
    d[x][y]=0
    while q:
        x,y=q.popleft()
        for k in range(4):
            nx,ny=x+dx[k],y+dy[k]
            # 격자 내, 출입 금지 아니며, 미탐색 지역이면 탐색
            if 0<=nx<n and 0<=ny<n and a[nx][ny]!=3 and d[nx][ny]==-1:
                d[nx][ny]=d[x][y]+1
                q.append([nx,ny])
                # 다음 위치 key 가 현재 위치를 value로 갖도록 경로 딕셔너리에 정보 추가
                parent[(nx,ny)]=(x,y)
    # 최단 경로
    trace = []
    current = (ex,ey)
    start=tuple(start)
    while current != start:
        trace.append(current)
        current = parent[current]
    trace.append(start)
    # 시작점부터 목적지까지
    trace.reverse()
    # 시작점 바로 다음 위치가 다음 갈 곳
    ans=trace[1]
    return ans

# 용도 : 편의점 -> 베이스캠프. 최단 경로
# input : 편의점 위치
# output : 베이스캠프 위치
def bfs2(x,y):
    global a
    ans = []
    q = deque()
    q.append([x, y])
    d = [[-1] * n for _ in range(n)]
    d[x][y] = 0
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < n and 0 <= ny < n and a[nx][ny] != 3 and d[nx][ny] == -1:
                d[nx][ny] = d[x][y] + 1
                q.append([nx, ny])
                if a[nx][ny]==1:
                    ans.append([d[nx][ny],nx,ny])
    ans.sort()
    return ans[0][1:]

while True:
    # 각 플레이어들의 숫자를 순차 탐색하며
    for no in range(1,len(pvisit)):
        # 해당 숫자의 플레이어가 이미 도착 상태라면 다음 플레이어로
        if pvisit[no]:
            continue
        # 이번 플레이어 선정
        p=players[no]
        # 이번 플레이어가 아직 격자 밖이라면 다음 플레이어로
        if (p.x,p.y)==(-1,-1):
            continue
        # 플레이어가 갈 위치 선정
        nx,ny=bfs1(p.x,p.y,p.ex,p.ey)
        # 플레이어 위치 업데이트
        p.x,p.y=nx,ny
        # 만약 플레이어가 향하던 편의점에 도착했다면
        if (p.x,p.y)==(p.ex,p.ey):
            # 맵에서 해당 위치는 출입금지로
            a[p.x][p.y]=3
            # 해당 플레이어는 도착 완료로 업데이트
            pvisit[p.no]=True
    # 현재 시간이 t분이고 t ≤ m를 만족한다면
    if t<=m:
        p=players[t]
        # 플레이어가 갈 베이스캠프 위치 선정
        bx,by=bfs2(p.ex,p.ey)
        # 해당 위치는 출입 금지로
        a[bx][by]=3
        # 플레이어는 베이스캠프로 위치
        p.x,p.y=bx,by
    # 플레이어들이 모두 도착 상태라면 중지
    if False not in pvisit:
        break
    t+=1

print(t)