코드트리 코드트리빵 | python | bfs 시작점 잘 파악하기

문제

링크

풀이

처음 제출하자마자 채점률이 쭉쭉 오르길래 디버깅 없이 1트에 성공하는 줄 알았는데 시간초과가 떠서 1시간 가량 헤메다 결국 정답 코드의 도움을 조금 빌렸다. 웃긴건 내 코드의 경우 대부분이 겪는 bfs로 인한 시간초과 때문이 아닌 것 같긴하다 ㅎ 해당 문제에선 bfs 최단경로를 파악해야 하는 부분이 크게 두 부분인데, 한 부분을 bfs 를 사용하지 않고 짜다가 로직이 살짝 꼬여버린 것이 틀린 이유인 것 같다.

그래도 구현 자체는 막히는 지점없이 1시간만에 완료했고, TC도 거의 다 맞추었다는 점에서 위안을 삼아본다

배열

board : 베이스 캠프가 있는 배열 (NxN)
lock : 더 이상 지나갈 수 없는 칸을 기록해 둔 배열 (NxN)

사실 board랑 lock이랑 충분히 합칠 수 있는데 입력받은 배열의 값을 변형하기 싫어서 분리해두었다. 본인이 이해하기 편한 방향으로 (안 헷갈리는 방향) 작성하면 될 듯 하다

people : 각 사람들의 현재 좌표가 저장된 1차원 배열
conv : 각 사람들이 가야할 편의점의 좌표가 저장된 1차원 배열

인덱스가 곧 특정 사람이 갖고 있는 id라고 생각하고 그 안의 좌표값만 바꿔줄 수 있도록 하였다. 헷갈리지 않도록 인덱스 0에는 무의미한 값을 집어넣었음

visited : bfs에서 방문 여부를 판단할 때 필요한 배열 (NxN)
step : bfs에서 방문 거리를 기록할 때 필요한 배열 (NxN)

사실 위 배열들은 bfs함수 내에서 로컬로 저장해두어도 무방하지만 1)해당 문제에서는 bfs를 두 번 진행한다는 점과 2)두 진행 방식에서 차이가 있기 때문에 전역으로 해두고 bfs를 진행할 때 마다 그 때 그 때 초기화하는 방식으로 구현하였다.

참고로 최단거리 정보를 저장하는 step도 visited랑 합쳐도 되지만 위에서 말한 것 처럼 최대한 관심사를 분리하고자 분리해두었다. 만약 합쳐서 생각하려면 visited를 0이 아닌 -1로 초기화해두고 visited[Y][X]=visited[y][x]-1 등으로 업데이트해주면 된다.

고려해야할 점

1. 최단거리 == bfs 는 국룰이다

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

   • 어짜피 한 칸만 움직이면 될 문제니까 조건문으로 잘 처리 해보면 되지 않을까 싶었는데 아니었다. 최단거리 보이면 무조건 bfs 진행하는걸로..
   • 우선 순위의 경우 문제에서 제시한 순서대로 방향 리스트를 초기화해두면 간단히 처리할 수 있다
   • 해당 문제에서는 사람들 움직일 때 bfs 한 번, 베이스캠프 고를 때 bfs 한 번 총 두 번 진행된다.

2. 시작점 잘 생각하기
   해당 문제는 bfs를 여러번 할 필요 없다는 것이 포인트이다. 이를 간과하면 bfs 시간 문제로 1솔을 하지 못할 수 있다.

   • 사람들 움직일 때
     • 타깃 편의점을 기준으로 모든 격자에 대한 거리를 구한 후, 거리가 가장 짧은 방향으로 사람이 이동 (0)
   • 베이스 캠프 고를 때
     • 베이스 캠프 별로 bfs를 진행해서 그 중 최소거리인 캠프 선정하기 (X)
       • 해당 경우가 bfs를 여러번 하는 경우가 되겠다
     • 타깃 편의점 기준으로 bfs 한 번만 진행해서 최소거리인 베이스캠프 선정하기 (0)
       • 이렇게 하면 bfs 한 번으로도 답을 구할 수 있다.

3. '모두' 이동 후 업데이트
   기출을 많이 풀지 않으면 초반에 많이 걸리는 오류일텐데, 대부분 삼성 기출문제는 사물/사람 이 특정 과정을 '모두' 진행하고 이후에 다음 과정이 진행되어야 하는 상황이 많다. 해당 문제에선 이 부분이 그렇게 중요한 점은 아니었지만 코드트리 지문에서 해당 부분을 강조해두어서 본인도 이를 간과하지 않기 위해 기록해둔다

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

4. 관심사를 분리해서 전역 배열을 여러개 만들어두자
   삼성 기출의 경우 입력 크기가 작기도 하고, 효율성보단 빡구현에 초점이 맞춰져 있으므로 하나의 배열만을 활용하여 그 안에 정보를 집어 넣기 보단 그냥 하나의 특성을 갖는 배열을 여러개 만들고 이를 이으려고 노력하자

코드

from collections import deque
n,m = map(int,input().split())
board=[]
for _ in range(n):
    board.append(list(map(int,input().split())))
lock=[[0]*n for _ in range(n)]

people=[(-1,-1) for _ in range(m+1)]
conv=[(-1,-1)]

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

# 편의점(도착지) 정보 위치
for _ in range(m):
    cy,cx = map(int,input().split())
    conv.append((cy-1,cx-1))

def isAllPassed():
    for i in range(1,m+1):
        if people[i]!=conv[i]:
            return False
    return True

d=[(-1,0),(0,-1),(0,1),(1,0)] # ↑, ←, →, ↓ 의 우선 순위

def bfs(sy,sx): # bfs 시작 좌표를 매개변수로 받아옴
    # visited, step 값을 전부 초기화합니다.
    for i in range(n):
        for j in range(n):
            visited[i][j] = 0
            step[i][j] = 0
    q = deque()
    q.append((sy, sx))
    visited[sy][sx] = 1
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y = y + dy
            X = x + dx
            if 0 <= Y < n and 0 <= X < n and not visited[Y][X] and lock[Y][X] == 0:
                visited[Y][X] = 1
                step[Y][X] = step[y][x] + 1
                q.append((Y, X))

def lock_board():
    for i in range(1,m+1):
        if people[i]==conv[i]:
            py,px=people[i]
            lock[py][px]=1



def enterBaseCamp(time):
    global m,n,d,board,people
    cy,cx=conv[time]
    bfs(cy, cx)
    dist = 1e9  # 최단거리값
    by, bx = -1, -1
    for i in range(n):
        for j in range(n):
            # 방문 가능한 베이스 캠프 중 거리가 가장 가까운 위치를 찾기
            if visited[i][j] and board[i][j] == 1 and dist > step[i][j]:
                dist = step[i][j]
                by,bx = i, j
    people[time]=(by,bx)
    lock[by][bx]=1
    # print(baseCamp[time],people[time])




def simulate():
    for i in range(1,m+1):
        # 아직 격자 밖에 있는 사람이거나 이미 편의점에 도착한 사람이라면 패스
        if people[i] == (-1,-1) or people[i] == conv[i]:
            continue
        cy,cx=conv[i]
        bfs(cy,cx)
        py,px = people[i]
        dist = 1e9
        ty, tx = -1, -1  # tmp 좌표
        for dy, dx in d:
            PY = py + dy
            PX = px + dx
            if 0 <= PY < n and 0 <= PX < n and visited[PY][PX] and dist > step[PY][PX]:
                dist = step[PY][PX]
                ty, tx = PY, PX
        people[i] = (ty, tx)
    lock_board()
    if time>m:
        return
    enterBaseCamp(time) 
    # print('1턴')
time=0
while 1:
    time+=1
    simulate()
    # 전부 이동이 끝났다면 종료
    if isAllPassed():
        break
print(time)