[Python/코테] 백준 28471 W키가 빠진 성원이

28471 W키가 빠진 성원이

문제 및 조건 설명: https://www.acmicpc.net/problem/28471

알고리즘 설계

💡idea.

• 배열을 순회하여 경로를 찾는 문제이므로 BFS를 적용할 수 있다.
• 시작점이 여러개이고, 방향이 상하좌우가 아닌 일곱개로 늘어났다.
  → 모든 시작점을 찾기 위해 여러 번 BFS를 반복하면 시간 복잡도가 $O(n^3)$ 이상이 될 것이다.
  → 그렇다면 거꾸로, 도착점(F)에서 시작하여 이동 가능한 모든 위치를 세어줄 수 있다.

🎲step.

1. 문제 조건에 맞게 BFS 함수를 정의한다.
   1. 방향은 7가지인데, F에서 시작해 거꾸로 이동할 것이므로  반대가 됨을 유의하자.
      (ex. A칸을 눌러서 온 것은, 오른쪽에서 온 것이다./ 결국 W키가 없다는 것은 F에서 시작해서 아래로 갈 수 없다는 것이다.)
   2. 큐에 원소가 push되면, 즉 방문하면 가능한 시작점이므로 cnt 변수를 1을 증가시킨다.
2. 시작점에서 BFS를 한 번 실행한다.

알고리즘 구현

❗해당 문제는 제출 시, pypy3으로 해야 한다. Python3로 제출하면 시간 초과가 뜬다.

from collections import deque
import sys

n = int(input())
map = [list(map(str, sys.stdin.readline().strip())) for _ in range(n)]


def bfs(x, y):
    dx = [-1, -1, 0, 0, 1, -1, 1]
    dy = [-1, 1, -1, 1, -1, 0, 1]
    queue = deque()
    queue.append((x, y))    # 도착지
    map[x][y] = "#"         # 방문 표시
    cnt = 0

    while queue:
        x, y = queue.popleft()

        for i in range(7):
            nx = dx[i]+x
            ny = dy[i]+y

            if 0 <= nx < n and 0 <= ny < n and map[nx][ny] != "#":
                queue.append((nx, ny))
                map[nx][ny] = "#"
                cnt += 1

    return cnt


cnt = 0

for i in range(n):
    for j in range(n):
        if map[i][j] == "F":
            cnt = bfs(i, j)
            break

print(cnt)

나다어

• 일이 너무 커질 땐(시간 복잡도가 너무 커지면) 딱 반대로 생각해보자.
• 이차원 배열을 입력받는 한 줄 수식을 잘 외워두자