[백준16946/골드2] 벽 부수고 이동하기 4 - Python

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

 

✅ 문제 조건

1. 0 : 이동 가능, 1 : 이동 불가능 (벽)
2. 벽을 부수고 이동할 수 있는 곳으로 변경
3. 그 위치에서 이동할 수 있는 칸의 개수 세기

 

정리하면 벽이 나타날때마다 그 벽을 포함해서 연결된 빈공간의 크기를 구하면 된다

 

✅ 접근 방법

 

방법 1)

각각의 칸마다 bfs 실행 -> 시간초과 O((N * M) * (N * M)) = O((N*M)^2)

전부 다 조건대로 구하면 되지만 그렇게 풀이하면 시간초과 난다.

 

 

방법 2)

1. 처음에 한번의 bfs 전체 순회하며 각 칸의 크기 측정

    (2667번 단지번호 붙이기 문제처럼 각 방의 고유번호를 측정, 고유번호는 0부터 시작)

2. 방의 고유번호를 다 붙였으면 그 붙인 크기를 리스트에 추가

    (고유번호는 0부터 시작하므로 리스트의 인덱스로 해당 방의 크기에 접근 가능)

3. 그리고 다시 배열을 처음부터 순회하며 벽이 나오면 상하좌우 탐색하여 방이 있는 경우 그 방의 크기의 합 구하기

 

 

✅ 구현

 

1. 빈방 그룹화

# 1. 각각의 연결된 빈공간 그룹화
group_id = 0
for i in range(N):
    for j in range(M):
        if mp[i][j] == '0' and group_mp[i][j] == -1:
            group_size.append(bfs(i, j, group_id))
            group_id += 1

# 그룹화 함수

group_mp = [[-1] * M for _ in range(N)]
group_size = []

def bfs(i, j, id):

    q = deque([(i, j)])
    group_mp[i][j] = id
    size = 1

    while q:
        ci, cj = q.popleft()

        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = ci + di, cj + dj

            if 0 <= ni < N and 0 <= nj < M and group_mp[ni][nj] == -1 and mp[ni][nj] == '0':
                group_mp[ni][nj] = id
                q.append((ni, nj))
                size += 1

    return size

 

 

2. 벽 부수고 이동하기

# 2. 각각의 벽 뚫었을때 상하좌루 그룹 탐색 후 크기 합치기
result = [['0'] * M for _ in range(N)]

for i in range(N):
    for j in range(M):
        if mp[i][j] == '1':
            result[i][j] = str(break_wall(i, j) % 10)

# 벽 주변 방의 크기 구하는 함수
def break_wall(i, j):
    cur_size = 1
    seen = set()

    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ni, nj = i + di, j + dj

        if 0 <= ni < N and 0 <= nj < M and mp[ni][nj] == '0':
            group_id = group_mp[ni][nj]
            if group_id not in seen:
                seen.add(group_id)
                cur_size += group_size[group_id]

    return cur_size

 

 

 

✅ 정답 코드

'''
조건)
0 : 이동 가능, 1 : 이동 불가능 (벽)
- 벽을 부수고 이동할 수 있는 곳으로 변경
- 그 위치에서 이동할 수 있는 칸의 개수 세기

풀이)
방법 1. 각각의 칸마다 bfs 실행 -> 시간초과 O((N * M) * (N * M)) = O((N*M)^2)
방법 2. 처음에 한번의 bfs 전체 순회하며 각 칸의 크기 측정 -> 다시 배열을 탐색하며 벽이 나타나면 측정한 칸의 크기의 합 구하기
'''

from collections import deque

N, M = map(int, input().split())
mp = [list(input()) for _ in range(N)]
group_mp = [[-1] * M for _ in range(N)]
group_size = []

# 그룹화 함수
def bfs(i, j, id):

    q = deque([(i, j)])
    group_mp[i][j] = id
    size = 1

    while q:
        ci, cj = q.popleft()

        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = ci + di, cj + dj

            if 0 <= ni < N and 0 <= nj < M and group_mp[ni][nj] == -1 and mp[ni][nj] == '0':
                group_mp[ni][nj] = id
                q.append((ni, nj))
                size += 1

    return size


# 벽 주변 방의 크기 구하는 함수
def break_wall(i, j):
    cur_size = 1
    seen = set()

    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ni, nj = i + di, j + dj

        if 0 <= ni < N and 0 <= nj < M and mp[ni][nj] == '0':
            group_id = group_mp[ni][nj]
            if group_id not in seen:
                seen.add(group_id)
                cur_size += group_size[group_id]

    return cur_size


# 1. 각각의 연결된 빈공간 그룹화
group_id = 0
for i in range(N):
    for j in range(M):
        if mp[i][j] == '0' and group_mp[i][j] == -1:
            group_size.append(bfs(i, j, group_id))
            group_id += 1


# 2. 각각의 벽 뚫었을때 상하좌루 그룹 탐색 후 크기 합치기
result = [['0'] * M for _ in range(N)]

for i in range(N):
    for j in range(M):
        if mp[i][j] == '1':
            result[i][j] = str(break_wall(i, j) % 10)

for line in result:
    print("".join(line))

 

 

 

처음엔 각 칸마다 크기와 그룹을 한번에 저장하려고 해서 구현이 좀 어려웠다.

그리고 다시 칸의 고유번호와 크기를 분리해서 저장하기까지의 시간이 많이 걸렸다.