[ baekjoon ] 가스관 2931번 ( python )

문제

백준 2931 가스관 풀이 ( 파이썬 )

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

2931번: 가스관

 

풀이

일단 입력을 받을 때 M이나 Z인 경우를 입력으로 받았다.

그리고 M과 Z인 좌표에서 시작하게 되는데

위 사진과 같이 일반적인 상황에서는 둘 중 하나에서 4방향 중 한 곳에 무조건 파이프를 갖게 된다 여기서 파이프를 갖게 된다는 말은 단순히 파이프가 있는 것이 아니라 흐를 수 있는 파이프가 있는 것이다. 그러므로 차례로 경로를 찾아가는 코드를 작성하면 된다.

하지만, 위의 경우처럼 옆에 둘 다 파이프가 없는 경우가 존재하는데,

이런 경우이다 그래서 flag라는 변수로 이 두 경우가 생길 수 있음을 생각하고 처음 나온 그림의 경우는 True로 두 번째인 경우는 False일 때로 생각해서 나눴다.

먼저 False일 때는 y좌표가 같은 지, 아니면 x좌표가 같은 지 생각해서 -나 |를 설치하면 된다.

 

True인 경우는 위에서 M이나 Z일 때 둘 중 하나는 무조건 흐르는 방향의 파이프가 존재하므로 그 파이프가 흐를 수 있는 방향을 따라서 흐를 수 있지만 .가 있는 경우를 찾으면 된다.

ax, ay가 잘못된 빈 공간의 .이다.(즉 먼저 .좌표를 찾는 과정임)

 

그리고 마지막에는 이 . 좌표의 4방향의 파이프를 확인해서 어떤 파이프가 좋은 지 결정하는 것이다.

from collections import deque

r, c = map(int,input().split())

def pip_list(pipe):
    if pipe == "|":
        return [0,2]
    if pipe == "-":
        return [1,3]
    if pipe == '+':
        return [0,1,2,3]
    if pipe == "1":
        return [1,2]
    if pipe == "2":
        return [0,1]
    if pipe == "3":
        return [0,3]
    if pipe == "4":
        return [2,3]

visited = [[False] * c for _ in range(r)]
arr = []
start = []

# 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(r):
    arr.append(list(input()))
    for j in range(c):
        if arr[i][j] == "M" or arr[i][j] == "Z":
            visited[i][j] == True
            start.append((i,j))
q = deque()

ax = 0
ay = 0

def bfs(q, visited):
    global ax, ay
    while q:
        x, y = q.popleft()
        visited[x][y] = True
        for i in pip_list(arr[x][y]):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= r or ny >= c or visited[nx][ny]:
                continue
            if arr[nx][ny] == "M" or arr[nx][ny] == "Z":
                continue
            if visited[nx][ny] == True:
                continue
            if arr[nx][ny] == '.':
                ax = nx
                ay = ny
            else:
                q.append((nx,ny))

flag=False

for s in start:
    x, y = s
    visited[x][y] = True
    # 북 동 남 서
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= r or ny >= c or visited[nx][ny]:
            continue
        if arr[nx][ny] != '.':
            flag = True
            if i == 0 and (arr[nx][ny] == '|' or arr[nx][ny] == '+' or arr[nx][ny] == '1' or arr[nx][ny] == '4'):
                q.append((nx,ny))
            if i == 1 and (arr[nx][ny] == '-' or arr[nx][ny] == '+' or arr[nx][ny] == '3' or arr[nx][ny] == '4'):
                q.append((nx,ny))
            if i == 2 and (arr[nx][ny] == '|' or arr[nx][ny] == '+' or arr[nx][ny] == '2' or arr[nx][ny] == '3'):
                q.append((nx,ny))
            if i == 3 and (arr[nx][ny] == '-' or arr[nx][ny] == '+' or arr[nx][ny] == '1' or arr[nx][ny] == '2'):
                q.append((nx,ny))
            
    if flag :
        bfs(q,visited)
        break
pipe=""
direction = [False]*4
[False, False, False, False]
if flag :
    # 북0 동1 남2 서3
    for i in range(4):
        nx = ax + dx[i]
        ny = ay + dy[i]
        if nx < 0 or ny < 0 or nx >= r or ny >= c:
            continue
        if i == 0 and (arr[nx][ny] == '|' or arr[nx][ny] == '+' or arr[nx][ny] == '1' or arr[nx][ny] == '4' ):
            direction[i] = True
        if i == 1 and (arr[nx][ny] == '-' or arr[nx][ny] == '+' or arr[nx][ny] == '3' or arr[nx][ny] == '4' ):
            direction[i] = True
        if i == 2 and (arr[nx][ny] == '|' or arr[nx][ny] == '+' or arr[nx][ny] == '2' or arr[nx][ny] == '3' ):
            direction[i] = True
        if i == 3 and (arr[nx][ny] == '-' or arr[nx][ny] == '+' or arr[nx][ny] == '1' or arr[nx][ny] == '2' ):
            direction[i] = True
    
    if direction[0] and direction[2] and not direction[1] and not direction[3]:
        pipe = "|"
    if direction[1] and direction[3] and not direction[0] and not direction[2]:
        pipe = "-"
    if direction[0] and direction[1] and direction[2] and direction[3]:
        pipe = "+"
    if direction[1] and direction[2] and not direction[0] and not direction[3]:
        pipe = "1"
    if direction[0] and direction[1] and not direction[2] and not direction[3]:
        pipe = "2"
    if direction[0] and direction[3] and not direction[1] and not direction[2]:
        pipe = "3"
    if direction[2] and direction[3] and not direction[0] and not direction[1]:
        pipe = "4"
else:
    if start[0][0] == start[1][0]:
        pipe = "-"
        ax = start[0][0]
        ay = (start[0][1] + start[1][1])//2
    else:
        pipe = "|"
        ax = (start[0][0] + start[1][0])//2
        ay = start[0][1]
print(ax+1,ay+1,pipe)