문제
[문제]
러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다.
두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.
이 게임에서 유럽은 R행 C열로 나누어져 있다.
각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다.
가스는 모스크바에서 자그레브로 흐른다. 가스는 블록을 통해 양방향으로 흐를 수 있다.
'+'는 특별한 블록으로, 아래 예시처럼 두 방향 (수직, 수평)으로 흘러야 한다.
파이프 라인의 설계를 마친 후 두 사람은 잠시 저녁을 먹으러 갔다. 그 사이 해커가 침임해 블록 하나를 지웠다. 지운 블록은 빈 칸이 되어있다.
해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블록이 있었는지 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 유럽의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 25)
다음 R개 줄에는 C개 글자가 주어지며, 다음과 같은 글자로 이루어져 있다.
- 빈칸을 나타내는 '.'
- 블록을 나타내는 '|'(아스키 124), '-','+','1','2','3','4'
- 모스크바의 위치를 나타내는 'M'과 자그레브를 나타내는 'Z'. 두 글자는 한 번만 주어진다.
항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어진다,
또, 모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다.
또, 불필요한 블록이 존재하지 않는다. 즉, 없어진 블록을 추가하면, 모든 블록에 가스가 흐르게 된다.
[출력]
지워진 블록의 행과 열 위치를 출력하고, 어떤 블록이었는지를 출력한다.아이디어
풀이 과정
-
블록이 끊기는 지점을 찾는다.
- 다음으로 파이프가 연결되어야 할 칸이 빈칸이라면, 이 위치가 블록이 끊기는 지점이다.
-
해당 지점의 상, 하, 좌, 우 블록을 보고 블록이 끊기는 지점에 들어갈 블록을 결정한다.
-
예를 들어, 어떤 파이프가 끊기는 위치가 다음과 같다면
-
상, 하, 좌, 우로 연결될 수 있는 부분을 찾는다.
-
해당 칸에 들어갈 블록은 위쪽, 오른쪽으로 연결되지 않고 아래쪽, 오른쪽으로 연결되는 4번 블록
-
끊긴 지점 기준으로 상, 하, 좌, 우 인접한 블록들을 통해 끊기는 지점의 블록을 도출하는 과정에서 주의할 점
- 인접한 블록 중 M, Z가 있다면 해당 블록들과 연결되지 않도록 한다.
- 문제에서 이미 '모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다.' 고 하였으므로
- 추가적으로 M, Z에 블록을 연결하지 않게 주의한다.
-
주의점
모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다.
제출 코드
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
arr = [list(input().strip()) for _ in range(n)]
# 0: 상, 1:하, 2: 좌, 3:우
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
# block_dirs['block'] = [상, 하, 좌, 우] 연결 가능 여부 1/0 표시
block_dirs = {'|':[1, 1, 0, 0],
'-':[0, 0, 1, 1],
'+':[1, 1, 1, 1],
'1':[0, 1, 0, 1],
'2':[1, 0, 0, 1],
'3':[1, 0, 1, 0],
'4':[0, 1, 1, 0],
'M':[1, 1, 1, 1],
'Z':[1, 1, 1, 1]}
# (r, c)에서 시작했을 때 연결이 끊기는 지점을 찾는다.
def find_diconnection():
mr = mc = -1
for r in range(n):
for c in range(m):
if arr[r][c] == 'M':
mr = r
mc = c
break
q = deque([(mr, mc)])
visited = [[False] * m for _ in range(n)]
visited[mr][mc] = True
while q:
r, c = q.popleft()
dirs = block_dirs[arr[r][c]]
for i in range(4):
if not dirs[i]:
continue
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < n and 0 <= nc < m:
if visited[nr][nc]:
continue
# 파이프가 연결되어야 하는 칸이 빈칸이라면 disconnection
if arr[nr][nc] == '.':
if arr[r][c] == 'M' or arr[r][c] == 'Z':
continue
else:
return (nr, nc)
visited[nr][nc] = True
q.append((nr, nc))
return (-1, -1)
def get_valid_block(target_r, target_c):
# (target_r, target_c)를 기준으로 상, 하, 좌, 우 블록들의 이동방향을 검사한다.
# target: (target_r, target_c)의 [상, 하, 좌, 우] 연결 가능 여부
target = [0, 0, 0, 0]
for i in range(4):
nr = target_r + dr[i]
nc = target_c + dc[i]
if 0 <= nr < n and 0 <= nc < m:
if arr[nr][nc] == '.':
continue
# 인접한 블록이 M이나 Z일때는 이 블록들과 연결되지 않도록 한다.
# 그 이유는, M/Z가 하나의 블록과 이미 인접해 있는 입력만 주어지기 때문에 다시 M/Z로 가는 블록을 연결해줄 필요가 없음.
if arr[nr][nc] == 'M' or arr[nr][nc] == 'Z':
target[i] = 0
continue
# 위에 있는 블록의 '하' 방향 연결 여부를 target[0]('상' 방향 연결 여부)에 저장
if i == 0:
target[0] = block_dirs[arr[nr][nc]][1]
# 아래에 있는 블록의 '상' 방향 연결 여부를 target[1]에 저장
elif i == 1:
target[1] = block_dirs[arr[nr][nc]][0]
# 좌측에 있는 블록의 '우' 방향 연결 여부를 target[2]에 저장
elif i == 2:
target[2] = block_dirs[arr[nr][nc]][3]
else:
target[3] = block_dirs[arr[nr][nc]][2]
# 완성된 target에 알맞은 블록을 리턴한다.
for block in block_dirs.keys():
if block_dirs[block] == target:
return block
return '.'
# 연결이 끊기는 지점
target_r, target_c = find_diconnection()
# 연결이 끊기는 지점에 어떤 블록을 넣어야 파이프라인이 완성될지
answer = get_valid_block(target_r, target_c)
print(target_r + 1, target_c + 1, answer)참고 사이트
코뉴로그