문제
[문제]
N×M의 행렬로 표현되는 맵이 있다.
맵에서 0은 이동할 수 있는 곳을 나타내고,
1은 이동할 수 없는 벽이 있는 곳을 나타낸다.
한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다.
두 칸이 변을 공유할 때, 인접하다고 한다.
각각의 벽에 대해서 다음을 구해보려고 한다.
- 벽을 부수고 이동할 수 있는 곳으로 변경한다.
- 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
[입력]
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다.
다음 N개의 줄에 M개의 숫자로 맵이 주어진다.
[출력]
맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고,
벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.아이디어
주의
문제를 봤을 때 가장 먼저 생각나는 풀이방법은 1(벽)인 모든 칸에서 BFS를 수행하는 것이다.
그러나 해당 방법으로 풀이하면 최악의 경우 N*M번 O(NM)인 BFS를 수행해야하므로 시간초과가 발생한다.
BFS
시간 안에 문제를 풀이하기 위해서, 1(벽)칸 기준이 아닌, 0(이동가능)칸을 기준으로 생각해보자.
-
예제 입력 2이다.
-
0끼리 영역을 이루고 있음을 알 수 있다. 보기 쉽게 색으로 구분해보자.
이를 코드로 작성하면, 방문하지 않은 0칸들에 대해 BFS를 수행하며 인접한 0칸들을 묶어 id를 부여하는 것과 같다. -
각 색깔을 id라고 하고, 해당 id에 속하는 칸수를 기록한다. 딕셔너리 자료구조를 이용한다.
-
이후, 각각의 1(벽)칸에서 인접한 id 영역에 속하는 칸수를 더해준 것이 해당 벽 칸을 부수고 이동했을 때 이동할 수 있는 칸의 개수이다.
위 이미지에서 노란 동그라미로 표시한 벽 칸을 부수고 이동했을 때,
회색 영역, 민트색 영역, 핑크색 영역에 있는 칸들로 이동할 수 있다.
따라서 기존 값 1에 인접한 영역들에 속한 칸의 개수를 더해주면 된다.
⭐️ 실제로 문제를 풀 때는, 10으로 나눈 나머지를 기록해야함에 유의하자.
제출 코드
Python
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
arr = [list(map(int, list(input().rstrip()))) for _ in range(n)]
dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]
# bfs
def bfs(r, c, visited, id):
q = deque([(r, c)])
visited[r][c] = id
# 칸의 개수
cnt = 0
while q:
r, c = q.popleft()
cnt += 1
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < n and 0 <= nc < m:
if visited[nr][nc] > 0:
continue
if arr[nr][nc] > 0:
continue
visited[nr][nc] = id
q.append((nr, nc))
return cnt
# 매번 벽에서 탐색을 수행하면 시간이 너무 오래걸린다.
# 0(이동할 수 있는 곳)을 기준으로 잡자. 0끼리 영역을 이룬다고 생각하자.
# 각 영역마다 id를 매겨주고, 해당 id를 가진 영역에 0인 칸이 몇개 포함되는지 기록하자.
visited = [[0] * m for _ in range(n)]
id = 1 # 초기 id
parts = dict()
for r in range(n):
for c in range(m):
if arr[r][c] == 0 and visited[r][c] == 0:
cnt = bfs(r, c, visited, id)
parts[id] = cnt
id += 1
# print("=== visited")
# for row in visited:
# print(row)
# print("=== parts:", parts)
# 1(벽)인 칸을 순회하며, parts[인접한id]를 더해준다.
for r in range(n):
for c in range(m):
if arr[r][c] == 1:
# 인접한 구역의 id들을 기록하는 집합
adj_ids = set()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < n and 0 <= nc < m:
if visited[nr][nc] == 0:
continue
adj_ids.add(visited[nr][nc])
for adj_id in adj_ids:
arr[r][c] += parts[adj_id]
arr[r][c] %= 10
# print("=== 결과")
# for row in arr:
# print(row)
for row in arr:
print(''.join(list(map(str, row))))참고 사이트
코뉴로그