16946: 벽 부수고 이동하기 4

문제 링크

16946: 벽 부수고 이동하기 4

구현 방식

1. 우선 벽이 있는 위치(board 값이 1)를 board 값을 -1로 변경해주었다

2. 그 후, board를 순회하면서, 이동할 수 있는 위치(board값이 0)마다 bfs 탐색으로 인접한 부분을 grouping 해주었다. 이 과정에서 group_info를 완성해주었다. group_info는 dictionary 형식으로, "group number": "group에 속해있는 칸의 개수"의 데이터들을 저장함

3. answer 2차원 list를 0으로 초기화해주고, board[x][y] == -1인 부분마다 get_sum을 호출해주어, 상하좌우 인접한 부분의 이동할 수 있는 칸의 개수를 세어주었다

코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline()[:-1].split())
board = [list(map(int, list(sys.stdin.readline()[:-1]))) for n in range(N)]

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def grouping(x, y, number):
    queue = deque([]); queue.append((x, y))
    visit[x][y] = True; board[x][y] = number

    cnt = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if not visit[nx][ny] and board[nx][ny] == 0:
                    visit[nx][ny] = True
                    queue.append((nx, ny))
                    board[nx][ny] = number; cnt += 1
    return cnt

def get_sum(x, y):
    sum_ = 1; visit = set()
    for i in range(4):
        nx = x + dx[i]; ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if board[nx][ny] > 0 and board[nx][ny] not in visit:  
                sum_ += group_info[board[nx][ny]]
                visit.add(board[nx][ny])
    answer[x][y] = sum_ % 10

for i in range(N):
    for j in range(M):
        if board[i][j] == 1: board[i][j] = -1

group_info = dict(); visit = [[False]*M for n in range(N)]; number = 1
for i in range(N):
    for j in range(M):
        if not visit[i][j] and board[i][j] == 0:
            group_info[number] = grouping(i, j, number)
            number += 1

answer = [[0]*M for n in range(N)]
for i in range(N):
    for j in range(M):
        if board[i][j] == -1:
            get_sum(i, j)

for n in range(N):
    print("".join(map(str, answer[n])))