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

문제

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

풀이

1) dfs for grouping

지도가 아래처럼 주어지면, 깊이우선탐색을 이용해 움직일 수 있는 경로를 그룹화 할 수 있다. 

1	1	0	0	1
0	0	1	1	1
0	1	0	1	0
1	0	1	0	1

1은 벽이므로 0에 대해서만 탐색하여, 그룹별 원소의 개수를 저장해둔다.

{g00 : 2, g10 : 3, g22 : 1, g24 : 1, g32 : 1, g33 : 1}

1	1	g00	g00	1
g10	g10	1	1	1
g10	1	g22	1	g24
1	g31	1	g33	1

2) memorization

특정 위치에서 이동할 수 있는 칸의 수는 주변(위, 아래, 왼쪽, 오른쪽)의 그룹을 참고하여 구할 수 있다.

예를 들어,
(0, 1)에서 출발했을때 도달할 수 있는 칸의 수
= 그룹 g00 원소의 개수 + 그룹 g10 원소의 개수 + (0, 1) 자신
= 2 + 3 + 1
= 6

 

(2, 1)에서 출발했을 때 도달할 수 있는 칸의 수

= 그룹 g10 원소의 개수 + 그룹 g22 원소 개수 + 그룹 g31 원소 개수 + (2, 1) 자신

= 3 + 1 + 1 + 1 = 6

1	1*	g00	g00	1
g10	g10	1	1	1
g10	1*	g22	1	g24
1	g31	1	g33	1

코드

import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
board = [list(map(int, input())) for i in range(N)]

answer = [[board[i][j] for j in range(M)] for i in range(N)]
check = lambda r, c : (0 <= r < N) and (0 <= c < M) # 범위 체크

def dfs(r, c) :
    if board[r][c] != 0 : return

    passed.add((r, c))
    board[r][c] = groupId # 그룹 아이디 세팅

    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
        nr, nc = r + dr, c + dc
        if check(nr, nc) : dfs(nr, nc)

# grouping
from collections import defaultdict
groupCountDict = defaultdict(int)
for i in range(N) :
    for j in range(M) :
        if board[i][j] != 0 : continue # 그룹핑되지 않고, 벽이 아닌 칸에서만

        passed = set()
        board[i][j] = 0
        groupId = "g%04d%04d"%(i, j) # 행과 열이 1000이하인 수이므로, 4자리수까지 고려
        dfs(i, j)

        groupCountDict[groupId] = len(passed) # 그룹별 원소의 개수 저장해 두기

# memorization
for i in range(N) : 
    for j in range(M) : 
        if board[i][j] == 1 :
            # 인접한 그룹 아이디 구하기
            aroundGroupSet = set()
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)] :
                nr, nc = i+dr, j+dc
                if not check(nr, nc) : continue # 테이블 범위를 벗어나지 않고
                if not str(board[nr][nc]).startswith("g") : continue # 그룹아이디가 저장되어 있을 때에만
                groupId = board[nr][nc] # 저장해둔 그룹아이디 꺼내기
                aroundGroupSet.add(groupId)

            # 그룹별 원소의 수 더하기
            for groupId in aroundGroupSet :
                answer[i][j] += groupCountDict[groupId]
             answer[i][j] %= 10

# 출력하기
for i in range(N) :
    print("".join(map(str, answer[i])))