[solved.ac 골드3] 2931_가스관 (파이썬, BFS, 시뮬레이션)

 

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

문제

러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.

이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다.

가스는 모스크바에서 자그레브로 흐른다. 가스는 블록을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블록으로, 아래 예시처럼 두 방향 (수직, 수평)으로 흘러야 한다.

파이프 라인의 설계를 마친 후 두 사람은 잠시 저녁을 먹으러 갔다. 그 사이 해커가 침임해 블록 하나를 지웠다. 지운 블록은 빈 칸이 되어있다.

해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블록이 있었는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 유럽의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 25)

다음 R개 줄에는 C개 글자가 주어지며, 다음과 같은 글자로 이루어져 있다.

• 빈칸을 나타내는 '.'
• 블록을 나타내는 '|'(아스키 124), '-','+','1','2','3','4'
• 모스크바의 위치를 나타내는 'M'과 자그레브를 나타내는 'Z'. 두 글자는 한 번만 주어진다.

항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어진다, 또, 모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다. 또, 불필요한 블록이 존재하지 않는다. 즉, 없어진 블록을 추가하면, 모든 블록에 가스가 흐르게 된다.

출력

지워진 블록의 행과 열 위치를 출력하고, 어떤 블록이었는지를 출력한다.

예제

---

나의 풀이

이 문제에서 주어지는 중요한 조건이 있다.

항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어진다, 또, 모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다. 또, 불필요한 블록이 존재하지 않는다. 즉, 없어진 블록을 추가하면, 모든 블록에 가스가 흐르게 된다.

위 조건에 따르면 정상적으로 연결되어 있는 파이프 중 딱 하나가 없어졌다는 것이다.

그럼 아주 간단하다.

1. M 부터 시작해서 파이프를 따라 이동한다
2. 갑자기 '.' 이 등장하면 해당 위치가 해킹당한 위치이다
3. 해킹당한 위치와 모양을 출력하면 된다.

해킹당한 위치의 모양은 어떻게 알 수 있을까?

이것도 역시 간단하다.

상, 하, 좌, 우 인접한 위치의 파이프 모양을 살펴보고 해킹당한 위치와 연결되고 있는 파이프를 찾아서 다시 이어주면 된다.

이렇게 해킹당한 위치로 연결되는 인접한 파이프가 있다면 다음과 같이 연결하면 된다.

 

해킹당한 위치를 찾는다 -> 인접한 위치의 모양을 보고 해킹당한 모양을 유추한다

 

전체 코드

from collections import deque
import sys

def input():
    return sys.stdin.readline().rstrip()

direct = {
    '|': [(-1, 0), (1, 0)],
    '-': [(0, -1), (0, 1)],
    '+': [(-1, 0), (1, 0), (0, -1), (0, 1)],
    '1': [(0, 1), (1, 0)],
    '2': [(-1, 0), (0, 1)],
    '3': [(-1, 0), (0, -1)],
    '4': [(0, -1), (1, 0)],
    'Z': []
}

def bfs(start):
    visited = [[False] * c for _ in range(r)]
    visited[start[0]][start[1]] = True
    q = deque()

    # 시작 파이프 찾기
    for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx, ny = start[0] + x, start[1] + y
        if nx in range(r) and ny in range(c) and arr[nx][ny] != '.':
            visited[nx][ny] = True
            q.append((nx, ny))

    # 탐색 시작
    while q:
        cx, cy = q.popleft()
        if arr[cx][cy] == '.':
            return cx, cy
        for x, y in direct[arr[cx][cy]]:
            nx, ny = cx + x, cy + y
            if nx in range(r) and ny in range(c) and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))

r, c = map(int, input().split())
arr = [list(input()) for _ in range(r)]

# find M
found = False
for i in range(r):
    for j in range(c):
        if arr[i][j] == 'M':
            M = (i, j)
            found = True
            break
    if found: break

mx, my = bfs(M)

p = [False] * 4 # 상, 하, 좌, 우

# 위
if mx - 1 in range(r) and arr[mx - 1][my] in ['|', '+', '1', '4']:
    p[0] = True
# 아래
if mx + 1 in range(r) and arr[mx + 1][my] in ['|', '+', '2', '3']:
    p[1] = True
# 왼쪽
if my - 1 in range(c) and arr[mx][my - 1] in ['-', '+', '1', '2']:
    p[2] = True
# 오른쪽
if my + 1 in range(c) and arr[mx][my + 1] in ['-', '+', '3', '4']:
    p[3] = True

# 이진수로 표현
num = 0
for i in range(4):
    if p[i]: num += 2 ** (3 - i)

# 해킹당한 파이프
hacked = {
    3: '-',
    5: '1',
    6: '4',
    9: '2',
    10: '3',
    12: '|',
    15: '+'
}

print(mx + 1, my + 1, hacked[num])

나는 모양을 유추하기 위해 p 라고 하는 리스트를 만들어서 상, 하, 좌, 우가 연결되어 있는지 여부를 체크했고, 이 값을 2진수로 바꾸어서 비교하는 방식을 사용했다.

채점 결과