[Python 알고리즘] 수영대회 결승전 - SWEA

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV

---

문제 분석

시작점부터 도착점까지 가장 빠른 길을 찾아야 한다. -> BFS
섬(1)은 지나갈 수 없다.
소용돌이(2)는 지나갈 수 없다. 다만 한 번 통과한 경우 지나갈 수 있다.
    소용돌이(2)는 0초부터 시작해서 2초 동안 유지되고 1초 동안 잠잠해지는 패턴을 반복한다.

 

접근

BFS 탐색을 하다가 소용돌이를 만났을 때는 판단을 해야 한다.
    방문한 위치인 경우 -> 지날 수 있다
    방문하지 않은 위치인 경우
        time % 3 == 2인 경우, 지날 수 있다
            이때 2를 0으로 바꿔야 한다. 한 번 방문한 뒤에는 언제든 지나갈 수 있기 때문에.
        나머지의 경우, 지날 수 없다.

BFS 탐색을 하는 경우
    큐에는 (x, y, time)이 담겨야 한다.
        그래야 최단 경로를 판단할 수 있기 때문에
    visited 배열은 (x, y, time)의 원소가 완벽하게 같은 경우 걸러낸다.

    4방향 탐색이 아니라, 가만히 있기를 포함한 5방향 탐색이기 때문에, 방문 여부를 결정하기 위해 time이 필요하다.

 

코드

from collections import deque

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

def bfs(a, b, time):
    q = deque()
    q.append((a, b, time))
    visited = []
    visited.append((a, b, time))

    while q:
        x, y, t = q.popleft()

        if x == ex and y == ey:
            return t

        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 matrix[nx][ny] == 1:
                continue

            if matrix[nx][ny] == 2:
                if t % 3 == 2:
                    matrix[nx][ny] = 0
                    q.append((nx, ny, t + 1))
                    visited.append((nx, ny, t + 1))
                else:
                    continue

            if (nx, ny, t + 1) not in visited:
                q.append((nx, ny, t + 1))
                visited.append((nx, ny, t + 1))


testCase = int(input())

for tc in range(testCase):
    n = int(input())
    matrix = [list(map(int, input().split())) for _ in range(n)]
    sx, sy = map(int, input().split())
    ex, ey = map(int, input().split())

    result = bfs(sx, sy, 0)
    print(f"#{tc + 1} {result}")

 

 

swea에서 해당 문제의 python 제출을 허용하지 않아, 정확한 정답 여부는 알 수 없다.

 

코테에서 유사한 문제를 풀었던 경험이 있어 어렵지 않게 풀었다.

"제자리에 있기"를 탐색 방향에 포함하는 것이 까다로운데, 시간까지 포함한 visited 배열로 관리하면 풀이할 수 있다.