#16946번 벽 부수고 이동하기 4 https://www.acmicpc.net/problem/16946
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이
www.acmicpc.net
내 첫 접근방법은 벽을 기록해놓은 뒤, 벽을 순회하면서 인접한 0을 세는 방식이었다.
틀린코드
from collections import deque
N, M = map(int, input().split())
maps = []
walls = deque()
for i in range(N):
tmp = input()
l = []
for j in range(M):
l.append(int(tmp[j]))
if int(tmp[j]) == 1:
walls.append([i, j])
maps.append(l)
def check(a, b):
result = 1
que = deque()
que.append([a, b])
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
visited = [[False]*M for _ in range(N)]
while que:
x, y = que.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
if maps[nx][ny] == 0:
visited[nx][ny] = True
que.append([nx, ny])
result += 1
else:
continue
maps[a][b] = result
for x, y in walls:
check(x, y)
for i in maps:
print("".join(map(str, i)))
시간초과가 났고, 나는 도저히 개선할 방안을 찾지 못해 다른 분들의 코드를 참고했다.
정답코드
from collections import deque
N, M = map(int, input().split())
# 지도
maps = [[int(x) for x in input()] for _ in range(N)]
# 0 위치 기록
zeros = []
# 답안 기록
answer = [[0]*M for _ in range(N)]
for i in range(N):
for j in range(M):
if maps[i][j] == 1:
answer[i][j] = 1
elif maps[i][j] == 0:
zeros.append([i,j])
# 방문 기록
visited = [[False]*M for _ in range(N)]
# 탐색 방향
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
def check(a, b):
# 0으로만 이루어진 구간 계산하기
result = 1 # 구간의 크기
que = deque()
que.append([a, b])
walls = []
while que:
x, y = que.popleft()
# 이동
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < M:
if visited[nx][ny]:
continue
visited[nx][ny] = True
if maps[nx][ny] == 0:
que.append([nx, ny])
result += 1
else:
# 인접한 벽 저장.
walls.append([nx, ny])
for x, y in walls:
visited[x][y] = False
answer[x][y] += result
if answer[x][y] >= 10:
answer[x][y] %= 10
# 0을 기준으로 순회
for x, y in zeros:
# 방문한 적이 있는 부분은 제외
if not visited[x][y]:
visited[x][y] = True
check(x, y)
for i in answer:
print("".join(map(str, i)))
접근방법 자체가 문제였다. 벽을 기준으로 연산을 진행하면 많은 중복이 발생한다.
이 때문에 0을 기록해놓은 뒤 이를 순회하면서 인접한 0들의 갯수를 인접한 벽에 기록한다.
그러니까, 구역별로 순회가 가능하다는 의미이다.
예제 2번을 예로 들면, (0,2)의 0이 처음 연산을 진행하게 되면,상하좌우에 존재하는 1,1, 0을 만난다.
1) walls 리스트에 두 1의 위치를 기록한다. (0,1), (1,2)
2) (0,3)은 0이기 때문에 result에 1을 더해주고
3) (0,3)을 기준으로 또 상하좌우 이동한다.
4) 좌 (0,2)은 이미 방문했으므로 패스 (visited 기록의 효과)
5) 우 (0,4), 하 (1,3) 은 1이기 때문에 walls에 기록한다.
6) 더 이상의 0은 존재하지 않는다. -> while 루프 종료
7) 답을 기록하는 answer리스트에 벽의 해당 좌표에 result를 더해준다.
8) 벽에 방문한 기록을 지워준다 (vistied 리스트) -> 왜냐하면, 다른 구역에서도 방문해야하기 때문이다.
9) 이렇게 0의 첫 구간 연산이 끝났다.
10) 다른 0중에서 방문한 적이 없는 0만을 대상으로 탐색을 지속한다.
그나마 깔끔하게 정리해봤다.
이렇게 보고 나니 쉽네..?
'Algorithm > acmicpc.net' 카테고리의 다른 글
오랜만에 만나 날 당황시키는 이분탐색 (실버3) (0) | 2022.02.25 |
---|---|
파이썬 시간초과의 늪..(골드3) (0) | 2022.02.24 |
골드가 익숙해지지 않아.. (골드4) (0) | 2022.02.22 |
라이브러리를 쓰는 이유 - 파이썬 (골드4) (0) | 2022.02.22 |
풀었지만 만족스럽지 못한 (골드 5) (0) | 2022.02.21 |