ABC 339 D번 복기 - 4차원 visited 배열 BFS 백트래킹

1. 문제

 

D - Synchronized Players (atcoder.jp)

D - Synchronized Players

 

 

2. 풀이

 

하라는대로 구현하면 된다

 

두 플레이어 P가 움직이는데 두 플레이어는 같은 방향으로 움직이게 되어있다.

 

또한 한 플레이어가 해당 방향으로 움직일수 없더라도 다른 플레이어가 움직일 수 있다면 움직이는 경우로 생각한다

 

그래서 먼저 두 플레이어의 위치를 찾고 BFS를 수행하는 전형적인 형태

 

n = int(stdin.readline())

maps = [list(stdin.readline().rstrip()) for _ in range(n)]

player = []

i = 1

for y in range(n):
    
    for x in range(n):
        
        if maps[y][x] == 'P':
            
            player.append((x,y,i))
            i += 1

print(bfs(player,maps,n))

 

 

BFS를 구현할 때 이제 생각을 조금 해야함

 

결국에 visited 처리를 해줘야 시간초과가 안날것인데 visited 처리를 어떻게 해줘야할것인가?

 

1) (x,y)와 (z,w)가 움직이는 형태이므로 visited[x][y][z][w]의 4차원 배열을 생각하면 될 것 같다.

 

이 때 map의 크기가 최대 60이니까 60*60*60*60 = 12960000정도로 1000만 정도면 선언이 가능할 것 같다

 

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

 

 

한 플레이어가 움직이지 못하더라도, 다른 플레이어가 움직일 수 있는데 그런 경우에도 움직이는 것으로 친다.

 

2) 그러면 한 플레이어의 이동 후 좌표 범위가 map을 벗어났거나, 이동했을때 장애물이 있다면, 이동하기 전 좌표로 되돌린다

 

for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:

    dx = x + a
    dy = y + b
    dz = z + a
    dw = w + b

    if dx < 0 or dx > n-1 or dy < 0 or dy > n-1 or maps[dy][dx] == '#':

        dx = x
        dy = y

    if dz < 0 or dz > n-1 or dw < 0 or dw > n-1 or maps[dw][dz] == '#':

        dz = z
        dw = w

 

 

최소로 이동하는 횟수를 구해야하기 때문에 각 경우에 대해서 count를 세줘야한다.

 

이동하고 나서 visited[dx][dy][dz][dw]가 0이라면 아직 방문하지 않은 곳이니까..

 

count + 1을 해줘야하는데

 

기본적인 실수를 해버렸단말이지

 

if visited[dx][dy][dz][dw] == 0:

    visited[dx][dy][dz][dw] = 1

    count += 1

    player = [(dx,dy,1),(dz,dw,2)]
    queue.append((player,count))

 

 

이렇게 해버린다면..?

 

(x,y) (z,w)에서 count일때

 

위로 가는 경우와 아래로 가는 경우, 오른쪽으로 가는 경우, 왼쪽으로 가는 경우 모두 count+1이 들어가야하는데

 

그냥 count+=1을 해버리면.. 

 

위로 가는 경우 count+1, 아래로 가는 경우 count+2 오른쪽으로 가는 경우 count+3, 왼쪽으로 가는 경우 count+4가 들어가잖아.

 

그래서 dcount = count+1로 해서.. 구별해줘야겠지

 

많이하던건데 실수했으니까 다시한번 짚고

 

if visited[dx][dy][dz][dw] == 0:

    visited[dx][dy][dz][dw] = 1

    dcount = count + 1

    if dx == dz and dy == dw:

        if answer > dcount:

            answer = dcount

    else:

        player = [(dx,dy,1),(dz,dw,2)]
        queue.append((player,dcount))

 

 

dx == dz, dy == dw이면 두 플레이어가 동일한 위치에 온 경우니까 count의 최솟값을 갱신해준다.

 

그리고나서는 queue에 넣지 말아야겠지

 

여기서 visited를 하지 말아야하냐 해야하냐 고민했는데..

 

더 최솟값으로 동일한 경우에 올수도 있으니까?

 

근데 그랬다면 더 빨리 갱신되었어야하니까 visited를 하는게 맞아

 

 

from collections import deque
from sys import stdin

def bfs(player,maps,n):
    
    visited = [[[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)] for _ in range(n)]

    count = 0
    queue = deque()
    queue.append((player,count))

    INF = 1000000000000000000000000000000000
    answer = INF

    while queue:
        
        player,count = queue.popleft()

        x = 0
        y = 0
        z = 0
        w = 0

        for a,b,i in player:
            
            if i == 1:
                
                x = a
                y = b
            
            else:
                
                z = a
                w = b
        
        for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:
            
            dx = x + a
            dy = y + b
            dz = z + a
            dw = w + b

            if dx < 0 or dx > n-1 or dy < 0 or dy > n-1 or maps[dy][dx] == '#':
                
                dx = x
                dy = y
            
            if dz < 0 or dz > n-1 or dw < 0 or dw > n-1 or maps[dw][dz] == '#':
                
                dz = z
                dw = w
            
            if visited[dx][dy][dz][dw] == 0:
                
                visited[dx][dy][dz][dw] = 1

                dcount = count + 1

                if dx == dz and dy == dw:
                    
                    if answer > dcount:
                        
                        answer = dcount
                
                else:

                    player = [(dx,dy,1),(dz,dw,2)]
                    queue.append((player,dcount))
    
    if answer == INF:
        
        answer = -1

    return answer

 

 

근데 이렇게하면 시간초과나더라

 

마지막으로 생각해볼 테크닉은 백트래킹이다.

 

행동횟수의 최솟값을 구하기 때문에.. 현재 행동횟수 count가 이미 갱신된 answer보다 크다면...

 

당연히 더 이상 볼필요도 없으니까 continue로 넘어가는 기본적인 백트래킹 테크닉을 적용

 

    while queue:
        
        player,count = queue.popleft()
        
        if count > answer:
            continue

        x = 0
        y = 0
        z = 0
        w = 0

        for a,b,i in player:
            
            if i == 1:
                
                x = a
                y = b
            
            else:
                
                z = a
                w = b