[백준 16946번] 파이썬 - 벽 부수고 이동하기 4

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

시간 제한 2초, 메모리 제한 512MB

# 조건

• N x M 행렬로 표현되는 맵이 있다.
• 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.
• 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다.
• 두 칸이 변을 공유할 때, 인접하다고 한다.
• 각각의 벽에 대해 아래를 구해보려고 한다.
  • 벽을 부수고 이동할 수 있는 곳으로 변경
  • 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

• 첫째 줄에 N(1<=N<=1000), M(1<=M<=1000) 주어진다.
• 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

• 맵의 형태로 정답을 출력
• 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

# 접근 방법

시간 초과

• bfs 이용하여 풀어준다.
• 현재 칸이 벽인 곳들을 순회하며, 움직일 수 있는 칸의 수를 세어준다.
• 벽인 칸을 임시로 0으로 변경해준 후, 탐색이 끝난다면 다시 1로 변경해준다.
• deepcopy를 이용하여 최초 원본을 복사해주고, max칸의 수를 변경하여 기록해준다.

import sys  
sys.stdin = open('input.txt')  
from copy import deepcopy  
from collections import deque  

di, dj = [1,-1,0,0],[0,0,-1,1]  

def bfs(si, sj):  
    cnt = 1  
    q = deque()  
    q.append((si, sj))  
    visited = [[0]*M for _ in range(N)]  
    visited[si][sj] = 1  
    while q:  
        ci, cj = q.popleft()  

        for d in range(4):  
            ni, nj = ci + di[d], cj+dj[d]  
            if 0<=ni<N and 0<=nj<M and visited[ni][nj] == 0 and arr[ni][nj] == 0:  
                q.append((ni, nj))  
                visited[ni][nj] = 1  
                cnt += 1  

    result[si][sj] = cnt  



N, M = map(int, input().split())  

arr = [list(map(int, input())) for _ in range(N)]  

result = deepcopy((arr))  

for i in range(N):  
    for j in range(M):  
        if arr[i][j]:  
            arr[i][j] = 0  
            bfs(i, j)  
            arr[i][j] = 1  


for k in result:  
    print(*k, sep='')

flood fill 알고리즘 사용

• 인접해 있는 0을 묶어서 그룹을 만들어 주고,
• 해당 그룹의 0의 개수를 dictionary에 저장해준다.
  • 또한, visited 배열에 해당 빈 칸이 어느 그룹에 속하는지 기록해준다.
• 보드를 돌며 1을 만나면 상하좌우 그룹의 0개수를 전부 더해서 출력하면 된다.
  • 중복을 제외하기 위해 set() 자료형 사용해준다.

import sys  
sys.stdin = open('input.txt')  
from copy import deepcopy  
from collections import deque, defaultdict  

di, dj = [1,-1,0,0],[0,0,-1,1]  

def bfs(si, sj):  
    global size  
    visited[si][sj] = size  
    q = deque()  
    q.append((si, sj))  
    while q:  
        ci, cj = q.popleft()  
        for d in range(4):  
            ni, nj = ci+di[d], cj+dj[d]  
            if 0<=ni<N and 0<=nj<M and visited[ni][nj] == 0 and arr[ni][nj] == 0:  
                q.append((ni, nj))  
                visited[ni][nj] = size  
                count[size] +=1  

    size += 1  

def check(si, sj):  
    add_num = set()  
    for d in range(4):  
        ni, nj = si+di[d], sj+dj[d]  
        if 0<=ni<N and 0<=nj<M:  
            add_num.add(visited[ni][nj])  

    val = 0  
    for u in add_num:  
        val += count[u]  

    result[si][sj] = (val+1) % 10  




N, M = map(int, input().split())  

arr = [list(map(int, input())) for _ in range(N)]  

result = deepcopy((arr))  
count = defaultdict(int)  
visited = [[0]*M for _ in range(N)]  
size = 1  
for i in range(N):  
    for j in range(M):  
        if not arr[i][j] and visited[i][j] == 0:  
            count[size] = 1  
            bfs(i, j)  

for k in range(N):  
    for l in range(M):  
        if arr[k][l]:  
            check(k,l)  


for k in result:  
    print(*k, sep='')