백준 - 벽부수고 이동하기4 16946(그래프,bfs, 골2)

문제 풀러가기

해당 문제는 bfs 문제 중에서 대표적인 유형 중 하나인 그룹핑 하기에 속한다. 단지번호붙이기 - 실버1 풀러가기

그러면 문제는 단순해진다. 먼저 그룹핑을 진행한 다음, 벽이 있는 곳에서 상하좌우 방향으로 그룹에 속한 벽들의 개수 + 1(자기 자신)을 더해주면 된다.

import sys
from collections import deque

def bfs(i,j,key):
    dq = deque()
    dq.append((i,j))
    visited[i][j] = key
    ret = 1

    while dq:
        x,y = dq.popleft()

        for i in range(4):
            nx,ny = x + dirx[i], y + diry[i],
            if 0 <= nx < N and 0 <= ny < M:
                if MAPS[nx][ny] == 0 and visited[nx][ny] == -1:
                    visited[nx][ny] = key
                    ret += 1
                    dq.append((nx,ny))

    return ret



N,M = map(int,sys.stdin.readline().split(' '))
MAPS = [list(map(int,list(sys.stdin.readline().strip()))) for _ in range(N)]
check = {} # 각 그룹의 대표 번호를 key로 하고 그룹에 속한 빈칸의 수를 value로 하는 dictionary
visited = [[-1 for _ in range(M)] for _ in range(N)] # 그룹 및 방문 정보 저장
dirx = [0,0,1,-1]
diry = [1,-1,0,0]

# 그룹핑 하기
for i in range(N):
    for j in range(M):
        key = i * M + j
        if MAPS[i][j] == 0 and visited[i][j] == -1:
            ret = bfs(i,j,key)
            check[key] = ret
            
# 정답 출력하기
for i in range(N):
    for j in range(M):
        if MAPS[i][j] == 0:
            print(0,end='')
        else:
            ret = 1
            tmp = set() # 같은 그룹을 여러번 더해주지 않기 위함.
            for _ in range(4):
                ni,nj = i + dirx[_] , j +diry[_]
                if 0 <= ni < N and 0<= nj < M:
                    key = ni * M + nj
                    if visited[ni][nj] != -1  and visited[ni][nj] not in tmp :
                        ret += check[visited[ni][nj]]
                        tmp.add(visited[ni][nj])

            print(ret % 10,end='')

    print()

문제를 잘 읽자 . 나머지 연산