[알고리즘] 벽 부수고 이동하기 4
난이도
Gold 2
문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.
각각의 벽에 대해서 다음을 구해보려고 한다.
벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.
출력
맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.
예제 입력
3 3
101
010
101
예제 출력
303
050
303
해설 및 후기
문제 구현은 단순해 보이나 시간 조건을 달성하는 것이 어려웠다. 첫 시도는 맵을 순회하면서 1이 탐지되면 그 주변을 DFS로 순회하며 총 개수를 구하는 것이었다. 그러나 이렇게 되면 0으로 이루어진 공간이 중복되어 게산되는 상황이 생겼고, 효율성이 매우 떨어지게 되었다.
때문에 맵을 일단 한번 순회하면서 그룹별로 나누고, 그 그룹에 해당하는 카운트 수를 다른 배열에 저장하였다. 이후 다시 맵을 순회하면서 1이 탐지되면 주변에 있는 그룹을 확인하고, 그 그룹에 존재하는 카운트 수를 모두 더하는 방식으로 진행했다. 결과에 10의 나머지가 출력되어야 한다는 것을 간과해서 몇 번 틀렸다.
제출 코드
import sys
sys.setrecursionlimit(10**7)
n,m = map(int, sys.stdin.readline().rstrip().split())
l = []
isVisit = [[False for _ in range(m)] for _ in range(n)]
cnt = 0
def init():
global isVisit, cnt
isVisit = [[False for _ in range(m)] for _ in range(n)]
cnt = 0
for i in range(n):
l.append(list(map(int,list(sys.stdin.readline().rstrip()))))
gc = 2
countGroup = [0,0]
def setValue(x,y,groupNum):
global cnt
cnt += 1
l[x][y] = groupNum
for i,j in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
if(i>=0 and j>=0 and i<n and j<m):
if(l[i][j] == 0):
setValue(i,j,groupNum)
def getVal(x,y):
usedGroups = []
ret = 1
for i,j in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
if(i>=0 and j>=0 and i<n and j<m):
if(l[i][j] != 1 and l[i][j] not in usedGroups):
ret += countGroup[l[i][j]]
usedGroups.append(l[i][j])
return ret%10
for i in range(n):
for j in range(m):
if(l[i][j] == 0):
cnt = 0
setValue(i,j,gc)
countGroup.append(cnt)
gc+=1
for i in range(n):
for j in range(m):
if(l[i][j] == 1):
print(getVal(i,j), end='')
else:
print(0, end='')
print()