백준 2931 가스관

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

구현 문제이다.
bfs를 통해 가스의 흐름을 찾아갈 수 있는데,
이때 블록을 어떻게 처리해야 할지가 문제이다. 블록마다 특정방향으로 흐를 수 있는데, 이 경우들을 고려해 블록마다 갈 수 있는 방향을 구하고 이 방향마다 bfs를 돌려주면 된다.

시작점M과 Z와 아직 방문하지 않은 블록을 bfs를 하면 한 지점으로 모이게 된다. 위치를 찾았으면 어떤 블록이 필요할지 골라야 하는데,
어떤 위치 x,y => nx,ny로 다음 위치를 파악할때 블록의 입장에서 보면 현재 온 방향의 반대방향으로 가는 블록이 있어야 하기 때문에 현재 들어온 방향과 반대방향을 블록 방향 후보에 넣어준다.

from collections import deque
r,c = map(int,input().split())
arr = []
sign = ['|','-','+','1','2','3','4']
dx = [-1,0,1,0]
dy = [0,1,0,-1]
visited = [[0]*c for i in range(r)]
bx=0; by=0; bdirection = []
def direction(s):
    if s == '|':
        return [0,2]
    elif s == 'M' or s == 'Z':
        return [0,1,2,3]
    elif s == '-':
        return [1,3]
    elif s == '+':
        return [0,1,2,3]
    elif s == '1':
        return [1,2]
    elif s == '2':
        return [0,1]
    elif s == '3':
        return [0,3]
    elif s == '4':
        return [2,3]

def bfs(x, y):
    global bx,by
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        visited[x][y] = 1
        dirs = direction(arr[x][y])
        for d in dirs:
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]:
                if arr[nx][ny] == '.':
                    if arr[x][y] == 'M' or arr[x][y] == 'Z':
                        continue
                    bx,by = nx,ny
                    bdirection.append((d+2)%4)
                else:
                    visited[nx][ny] = 1
                    queue.append((nx,ny))

for i in range(r):
    row = list(input())
    for j in range(c):
        if row[j] == 'M':
            m = (i,j)
        elif row[j] == 'Z':
            z = (i,j)
    arr.append(row)
bfs(m[0],m[1])
bfs(z[0],z[1])

for i in range(r):
    for j in range(c):
        if arr[i][j] != '.' and not visited[i][j]:
            bfs(i,j)

bdirection = list(set(bdirection))
bdirection.sort()
for s in sign:
    if bdirection == direction(s):
        print(bx+1,by+1,s)