가스관 (2931번) - 백준 (BOJ)

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

2931번: 가스관

 

백준 - 가스관 (CIJEVI) (2931번)

 

난이도 : Gold 3

알고리즘&자료구조 : Simulation (구현)

---

★ 핵심 Idea ★

M에서 출발해서 파이프를 쭉 따라가며 중간에 끊긴 좌표를 찾고,

그 좌표의 상하좌우를 확인하면서 알맞은 모양의 파이프를 찾는다.

 

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline


class Pipe():
    def __init__(self, R, C):
        self.R, self.C = R, C
        dd = [[-1, 0, 1, 0], [0, 1, 0, -1]]
        mapping = {0: 2, 1: 3, 2: 0, 3: 1}
        r, c = self._init_board()
        for i in range(4):
            if 0 <= r+dd[0][i] < self.R and 0 <= c+dd[1][i] < self.C:
                if self.board[r+dd[0][i]][c+dd[1][i]] not in ('.', 'Z'):
                    r, c, inway = r+dd[0][i], c+dd[1][i], mapping[i]
                    break
        while self.board[r][c] != '.':
            inway = self._get_next_inway(inway, r, c)
            r, c = r+dd[0][mapping[inway]], c+dd[1][mapping[inway]]
        
        links = []
        poss = [
            ("|", "+", "1", "4"), ("-", "+", "3", "4"), ("|", "+", "2", "3"), ("-", "+", "1", "2")
        ]
        for i in range(4):
            if 0 <= r+dd[0][i] < self.R and 0 <= c+dd[1][i] < self.C:
                if self.board[r+dd[0][i]][c+dd[1][i]] in poss[i]:
                    links.append(i)
        if len(links) == 4:
            shape = "+"
        else:
            if links == [0, 1]:
                shape = "2"
            elif links == [0, 2]:
                shape = "|"
            elif links == [0, 3]:
                shape = "3"
            elif links == [1, 2]:
                shape = "1"
            elif links == [1, 3]:
                shape = "-"
            elif links == [2, 3]:
                shape = "4"
        self.hacked = (r+1, c+1, shape)


    def _init_board(self):
        self.board = [input().rstrip() for _ in range(self.R)]
        for r in range(self.R):
            for c in range(self.C):
                if self.board[r][c] == 'M':
                    return (r, c)

    
    def _get_next_inway(self, inway, r, c):
        if self.board[r][c] == '|':
            return 2 if inway == 2 else 0
        if self.board[r][c] == '-':
            return 3 if inway == 3 else 1
        if self.board[r][c] == '+':
            return inway
        if self.board[r][c] == '1':
            return 3 if inway == 2 else 0
        if self.board[r][c] == '2':
            return 3 if inway == 0 else 2
        if self.board[r][c] == '3':
            return 1 if inway == 0 else 2
        if self.board[r][c] == '4':
            return 1 if inway == 2 else 0


if __name__ == '__main__':
    pipes = Pipe(*map(int, input().split()))
    print(*pipes.hacked)

---

 

① "M"의 위치를 찾고, "M"과 인접한 파이프로 이동한다.

(이 때, "inway"에 이동 방향을 기록해둔다.)

 

def _init_board(self):
    self.board = [input().rstrip() for _ in range(self.R)]
    for r in range(self.R):
        for c in range(self.C):
            if self.board[r][c] == 'M':
                return (r, c)

self.R, self.C = R, C
dd = [[-1, 0, 1, 0], [0, 1, 0, -1]]
mapping = {0: 2, 1: 3, 2: 0, 3: 1}
r, c = self._init_board()
for i in range(4):
    if 0 <= r+dd[0][i] < self.R and 0 <= c+dd[1][i] < self.C:
        if self.board[r+dd[0][i]][c+dd[1][i]] not in ('.', 'Z'):
            r, c, inway = r+dd[0][i], c+dd[1][i], mapping[i]
            break

 

 

 

② 파이프의 좌표와 이동 방향을 고려하면서,

중간에 끊기는 부분에 도달하기 전까지 계속 이동한다.

 

def _get_next_inway(self, inway, r, c):
    if self.board[r][c] == '|':
        return 2 if inway == 2 else 0
    if self.board[r][c] == '-':
        return 3 if inway == 3 else 1
    if self.board[r][c] == '+':
        return inway
    if self.board[r][c] == '1':
        return 3 if inway == 2 else 0
    if self.board[r][c] == '2':
        return 3 if inway == 0 else 2
    if self.board[r][c] == '3':
        return 1 if inway == 0 else 2
    if self.board[r][c] == '4':
        return 1 if inway == 2 else 0


while self.board[r][c] != '.':
    inway = self._get_next_inway(inway, r, c)
    r, c = r+dd[0][mapping[inway]], c+dd[1][mapping[inway]]

 

 

 

③ 끊긴 부분에 도달하면, 상하좌우에 연결 가능한 파이프를 확인하고

인접한 파이프에 모두 연결될 수 있는 모양의 파이프를 "shape"에 기록한다.

 

links = []
poss = [
    ("|", "+", "1", "4"), ("-", "+", "3", "4"), ("|", "+", "2", "3"), ("-", "+", "1", "2")
]
for i in range(4):
    if 0 <= r+dd[0][i] < self.R and 0 <= c+dd[1][i] < self.C:
        if self.board[r+dd[0][i]][c+dd[1][i]] in poss[i]:
            links.append(i)
if len(links) == 4:
    shape = "+"
else:
    if links == [0, 1]:
        shape = "2"
    elif links == [0, 2]:
        shape = "|"
    elif links == [0, 3]:
        shape = "3"
    elif links == [1, 2]:
        shape = "1"
    elif links == [1, 3]:
        shape = "-"
    elif links == [2, 3]:
        shape = "4"

 

 

 

④ 파이프가 끊어지 곳의 좌표와, 파이프의 모양을 출력한다.

 

self.hacked = (r+1, c+1, shape)
print(*pipes.hacked)