[백준 - Python] 16946 - 벽 부수고 이동하기 4

0. 문제 링크

 

 

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

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

---

1. 풀이 방법

 

 

 

우선 0이 있을 때, 해당 0과 인접한 0을 모두 읽었다.

당연히 방문 표시는 했고, 이때 방문한 0의 위치를 모두 좌표로 저장했다.

그리고 나서 다시 방문하면서 그룹 번호와 개수를 부여했다.

그룹 번호는 참고로 복소수의 허수 부분으로 대체했다.

이렇게 하면 특정 위치의 0에 대해서, 이 0이 속한 그룹의 0의 개수와 그룹 번호도 알 수 있다.

 

그 다음에,

이중 for loop를 돌면서 1이라면 내 상하좌우에 있는 0의 개수를 더했다.

당연한 말이지만 1이 하나의 그룹으로 둘러싸인 경우도 고려해야 한다.

따라서 이미 특정 그룹의 개수로 더해진 1이라면, 그룹 번호까지 기억해서 중복으로 더하지 않게 했다.

마지막은 출력 양식에 맞춰서 수정했다.

---

2. 코드

 

 

from collections import deque

n, m = map(int, input().split())
board = []
dq = deque()
visited = deque()
dir = [[-1, 0], [0, 1], [1, 0], [0, -1]]

for i in range(n):
    t = list(map(int, list(input())))
    board.append(t)

cnt_imag = 1j       # 그룹 번호, 1이 0으로 둘러싸인 경우를 피하기 위해
for i in range(n):
    for j in range(m):
        if board[i][j] == 0:        # 0이라면 인접한 0의 개수를 모두 찾음
            cnt = 1
            dq.append([i, j])
            visited.append([i, j])      # 방문한 0의 좌표들을 모아놓음
            board[i][j] = -1        # 방문 표시함
            while dq:
                cur_i, cur_j = dq.popleft()
                for next_dir in dir:
                    next_i = cur_i + next_dir[0]
                    next_j = cur_j + next_dir[1]
                    if 0 <= next_i < n and 0 <= next_j < m and not board[next_i][next_j]:
                        # 방문할 곳의 값이 0이라면
                        dq.append([next_i, next_j])
                        visited.append([next_i, next_j])        # 방문한 좌표
                        board[next_i][next_j] = -1      # 방문 표시
                        cnt += 1
            while visited:      # 방문한 0의 좌표를 모두 그룹 갯수로 바꿈
                v = visited.popleft()
                board[v[0]][v[1]] = cnt + cnt_imag      # 인접한 0의 개수와 그룹 번호를 따로 넣음, 0은 모두 그룹화됨
            cnt_imag += 1j      # 그룹 번호 변경

for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            for next_dir in dir:
                next_i = i + next_dir[0]
                next_j = j + next_dir[1]
                if 0 <= next_i < n and 0 <= next_j < m:
                    if imag := board[next_i][next_j].imag:      # 인접한 애들의 그룹 번호이 있다면
                        if imag not in visited:
                            visited.append(imag)        # 해당 그룹은 두 번 이상 더할 필요가 없음
                            board[i][j] += int(board[next_i][next_j].real)      # 근처에 있는 0의 개수를 더함
            visited.clear()
            board[i][j] %= 10

board = list(map(lambda x: 0 if x.imag > 0 else x, board[i]) for i in range(n))     # 그룹이 있다면 0이므로 0으로 바꿈

for i in board:
    print(*i, sep='')

---

3. 마무리

 

 

참고로 복소수를 쓰는 것 보다, 딕셔너리를 사용해서 그냥 그룹 번호만 집어넣는 것이 훨씬 효율적이라고 생각한다.