[BaekJoon] 16946 벽 부수고 이동하기 4 (Gold 2) - Python

문제

 

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

---

입출력 예시

 

입력: 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

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

 

입력예시1)

3 3
101
010
101

출력예시1)

303
050
303

 

입력예시2)

4 5
11001
00111
01010
10101

출력예시2)

46003
00732
06040
50403

 

---

코드

 

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().rstrip().split()) # N, M 입력
grid = [list(map(int, list(input().rstrip()))) for _ in range(N)] # grid 입력
visited = [[False for _ in range(M)] for _ in range(N)] # 방문 리스트 생성
zero = [[0 for _ in range(M)] for _ in range(N)] # 0의 개수 리스트 생성
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)] # x, y변화량 리스트 생성
group = 1 # 0 그룹 이름 생성
info = dict() # 0 그룹 저장할 딕셔너리 생성

def BFS(x, y): # 0 그룹: 0의 개수를 리턴하는 bfs함수 작성

    q = deque()
    q.append([x, y])
    visited[x][y] = True
    cnt = 1

    while q:
        x, y = q.pop()
        zero[x][y] = group 
        for dx, dy in dir:
            nx, ny = x + dx, y + dy
            if nx < 0 or ny < 0 or nx >= N or ny >= M: continue
            if visited[nx][ny]: continue
            if not grid[nx][ny]: 
                q.append([nx, ny])
                visited[nx][ny] = True
                cnt += 1
    return cnt

def check(x, y): # 갈 수 있는 방의 수를 리턴하는 함수 

    buf = set()
    for dx, dy in dir:
        nx, ny = x + dx, y + dy
        if nx < 0 or ny < 0 or nx >= N or ny >= M: continue
        if not zero[nx][ny]: continue
        buf.add(zero[nx][ny])
    cnt = 1
    for c in buf:
        cnt += info[c]
        cnt = cnt % 10
    return cnt

# 먼저 grid의 0들을 그룹으로 묶어서 딕셔너리에 그 그룹에 몇 개의 0이 들어있는지 저장한다.
for i in range(N):
    for j in range(M):
        if not grid[i][j] and not visited[i][j]: 
            cnt = BFS(i, j)
            info[group] = cnt
            group += 1

# grid의 상하좌우를 확인하며 0그룹이 있는지, 있다면 0이 몇 개 있는지를 더하여 ans에 저장한다.
ans = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
    for j in range(M):
        if grid[i][j]:
            ans[i][j] = check(i, j)

# 결과값 출력
for i in range(N):
    print(''.join(map(str, ans[i])))

---

실행 화면

 

---

채점 결과

처음에 냅다 bfs랑 브루트포스로 개수 출력했는데 시간초과 뜸

찾아보니까 무슨 플러드필(Flood Fill)알고리즘 이라던데 ,,,

나중에 찾아봐야지 ㅇ.ㅇ