벽 부수고 이동하기 4 (16946번) - 백준 (BOJ)

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

16946번: 벽 부수고 이동하기 4

 

 

백준 - 벽 부수고 이동하기 4 (16946번)

 

난이도 : Gold 2

알고리즘&자료구조 : DFS (깊이우선탐색)

---

★ 핵심 Idea ★

 

◎ 벽이 아닌 빈 곳들을 그룹화하고, 각 그룹의 칸 수를 기록한다.

 

이후 각 벽을 기준으로 상하좌우 빈 칸의 그룹들을 확인하고,

서로 다른 그룹들의 칸 수를 모두 더하고 마지막에 1을 더해주면,

해당 벽을 부쉈을 때 이동할 수 있는 칸의 수가 된다.

 

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline
from copy import deepcopy


class Maapp():
    def __init__(self, N, M):
        self.board = [list(map(int, input().rstrip())) for _ in range(N)]
        self.answer = deepcopy(self.board)
        group_count = [0, 0]
        self.N, self.M = N, M
        n_grp = 2
        for r in range(N):
            for c in range(M):
                if self.board[r][c]:
                    continue
                group_count.append(self._crash(n_grp, r, c))
                n_grp += 1
        for r in range(N):
            for c in range(M):
                if not self.answer[r][c]:
                    continue
                n_grp = {self.board[rr][cc] for rr, cc in self._adjs(r, c)}
                self.answer[r][c] = (sum(group_count[grp] for grp in n_grp) + 1) % 10

    
    def _crash(self, grp, r, c):
        cnt = 1
        self.board[r][c] = grp
        stack = [(r, c)]
        while stack:
            r, c = stack.pop()
            for rr, cc in self._adjs(r, c):
                if self.board[rr][cc]:
                    continue
                self.board[rr][cc] = grp
                cnt += 1
                stack.append((rr, cc))
        return cnt


    def _adjs(self, r, c):
        if r > 0:  yield r-1, c
        if c > 0:  yield r, c-1
        if r < self.N-1:  yield r+1, c
        if c < self.M-1:  yield r, c+1


if __name__ == '__main__':
    _map = Maapp(*map(int, input().split()))
    print('\n'.join(''.join(map(str, row)) for row in _map.answer))

 

 

---

 

① 서로 연결되어있는 빈 칸들을 그룹화하고, 각 그룹의 칸 수를 "group_count"에 기록한다.

이 때, DFS (stack) 을 활용한다. (BFS를 활용해도 상관없다.)

 

def _crash(self, grp, r, c):
    cnt = 1
    self.board[r][c] = grp
    stack = [(r, c)]
    while stack:
        r, c = stack.pop()
        for rr, cc in self._adjs(r, c):
            if self.board[rr][cc]:
                continue
            self.board[rr][cc] = grp
            cnt += 1
            stack.append((rr, cc))
    return cnt


self.board = [list(map(int, input().rstrip())) for _ in range(N)]
self.answer = deepcopy(self.board)
group_count = [0, 0]
self.N, self.M = N, M
n_grp = 2
for r in range(N):
    for c in range(M):
        if self.board[r][c]:
            continue
        group_count.append(self._crash(n_grp, r, c))
        n_grp += 1

 

 

 

② 각 벽의 상하좌우 빈 칸을 확인하고, 각 빈 칸이 속한 서로 다른 그룹들의 칸 수를 모두 더하고 1을 더한다.

그 값이 해당 벽을 부쉈을 때, 이동할 수 있는 칸의 수가 된다.

 

for r in range(N):
    for c in range(M):
        if not self.answer[r][c]:
            continue
        n_grp = {self.board[rr][cc] for rr, cc in self._adjs(r, c)}
        self.answer[r][c] = (sum(group_count[grp] for grp in n_grp) + 1) % 10

 

 

 

③ 상하좌우 인접 칸으로 이동할 때, N행 M열의 범위를 벗어나지 않도록 "_adj" 함수를 작성한다.

 

def _adjs(self, r, c):
    if r > 0:  yield r-1, c
    if c > 0:  yield r, c-1
    if r < self.N-1:  yield r+1, c
    if c < self.M-1:  yield r, c+1

 

 

 

④ 각 벽을 부쉈을 때 이동할 수 있는 칸 수를 기록한 "answer"을

출력 형식에 맞게 변환해서 출력한다.

 

print('\n'.join(''.join(map(str, row)) for row in _map.answer))