백준 16946 벽 부수고 이동하기 4

문제

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

코드

from collections import deque
input = __import__('sys').stdin.readline


def bfs(y, x):
    q = deque()
    q.append((y, x))
    temp[y][x] = num
    cnt = 1
    while q:
        nowy, nowx = q.popleft()

        for i in range(4):
            newy = d[i][0]+nowy
            newx = d[i][1]+nowx
            if newy < 0 or newy >= n or newx < 0 or newx >= m or board[newy][newx] != 0 or temp[newy][newx] != 0:
                continue
            temp[newy][newx] = num
            q.append((newy, newx))
            cnt += 1
    return cnt


n, m = map(int, input().split())
board = [list(map(int, input().strip())) for _ in range(n)]
temp = [[0]*m for _ in range(n)]

d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
cnts = {}
num = 1
for i in range(n):
    for j in range(m):
        if board[i][j] == 1 or temp[i][j] != 0:
            continue
        cnt = bfs(i, j)
        cnts[num] = cnt
        num += 1


for i in range(n):
    for j in range(m):
        if board[i][j] == 0:
            continue

        group_list = set()
        for di in range(4):
            newy = d[di][0]+i
            newx = d[di][1]+j
            if newy < 0 or newy >= n or newx < 0 or newx >= m or temp[newy][newx] == 0:
                continue
            group_list.add(temp[newy][newx])
        for k in group_list:
            board[i][j] += cnts[k]
            board[i][j] %= 10


result = ''
for i in board:
    result += ''.join(map(str, i))+'\n'
print(result)

풀이

dfs,bfs를 사용한 풀이

가장 처음 접근은 dfs를 사용했습니다 현재 좌표값이 1일 경우 dfs를 통해서 연결되어 있는 0값들을 카운팅해서 board[i][j]를 수정했습니다 정답은 맞았는데 시간초과가 떴구요 구글에 검색해서 풀이법을 찾아봤습니다

시간을 단축하기 위해 0이 연속적으로 있는 구역들을 그룹핑해서 저장 후 카운팅

bfs를 통해 0의 범위들에게 그룹번호를 지정해줍니다 예를 들어 문제 2번 예시인

4 5 
11001
00111 
01010 
10101

입력이 들어 왔을 경우 temp는

00110 
22000 
20304 
05060

이렇게 저장이 되는데 저 구역의 번호를 저장해논거에요

그리고 그룹번호를 인덱스로 리스트나 딕셔너리를 만들어서 구역의 크기를 저장해줍니다

print(list) #[0,2,3,1,1,1,1]

이런식으로 나오겠네요 1번 그룹의 0의 개수는 2개, 2번 그룹의 0의 개수는 3개~~

그 후에 board를 순회돌면서 4방향의 그룹번호에 해당하는 값을 더해주면 됩니다

후기

bfs 함수를 잘못 설계해서 2시간동안 문제를 찾았네요 이번 문제처럼 영역을 찾는 알고리즘을 플러드 필이라고 부른다고 합니다 영역을 그룹핑해서 시간을 단축시키는 방법은 아마 혼자서는 생각하지 못했을 거 같아요

2시간동안 힘들었지만 그래도 많이 배운거같아서 뿌듯합니다 하하