백준 2931 가스관 (파이썬)

https://www.acmicpc.net/problem/2931

2931번: 가스관

1. 각 가스관에서 다음칸으로 이동할 수 있는 방향을 direction 함수에 저장

2. M의 좌표에서 bfs를 실행하고 Z의 좌표에서 bfs를 실행한다

3. 가스관이 설치되있는데 bfs로 방문한 기록이 없으면 그 좌표에서 bfs를 실행한다

4. bfs에서는 다음칸이 . 이면 그 칸에 가스관을 설치해야하므로 해당 칸의 좌표를 저장하고

  어느 방향으로 연결해야하는지를 check_list에 저장한다

5. check_list에 요소가 4개이면 필요한 가스관이 + 이고 다른 경우에는 가스관을 하나씩 대입해보면서

  check_list에 저장된 방향과 일치하는지 검사 후 출력한다

from collections import deque
import sys

input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def direction(s):
    if s == '|':
        return [1, 3]
    elif s == '-':
        return [0, 2]
    elif s == '+' or s == 'M' or s == 'Z':
        return [0, 1, 2, 3]
    elif s == '1':
        return [0, 1]
    elif s == '2':
        return [0, 3]
    elif s == '3':
        return [2, 3]
    elif s == '4':
        return [1, 2]

def bfs(x, y, dir):
    global fx, fy
    q = deque()
    q.append([x, y, dir])
    c[x][y] = 1
    while q:
        x, y, dir = q.popleft()
        for d in dir:
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < m and 0 <= ny < n and not c[nx][ny]:
                if a[nx][ny] != '.':
                    c[nx][ny] = 1
                    ndir = direction(a[nx][ny])
                    q.append([nx, ny, ndir])
                else:
                    if a[x][y] == 'M' or a[x][y] == 'Z':
                        continue
                    if not fx and not fy:
                        fx, fy = nx + 1, ny + 1
                    nd = (d+2) % 4
                    if nd not in check_list:
                        check_list.append(nd)

m, n = map(int, input().split())
c = [[0] * n for _ in range(m)]

a = []
for i in range(m):
    row = list(input().strip())
    a.append(row)
    for j in range(n):
        if row[j] == 'M':
            sx, sy = i, j
        elif row[j] == 'Z':
            zx, zy = i, j

check_list, fx, fy = [], 0, 0
bfs(sx, sy, [0, 1, 2, 3])
bfs(zx, zy, [0, 1, 2, 3])

for i in range(m):
    for j in range(n):
        if a[i][j] != '.' and not c[i][j]:
            bfs(i, j, direction(a[i][j]))
check_list.sort()

if len(check_list) == 4:
    print(fx, fy, '+')
else:
    block_list = ['|', '-', '1', '2', '3', '4']
    for s in block_list:
        if check_list == direction(s):
            print(fx, fy, s)