골드2... 판단미스

#16946번 벽 부수고 이동하기 4 https://www.acmicpc.net/problem/16946

16946번: 벽 부수고 이동하기 4

내 첫 접근방법은 벽을 기록해놓은 뒤, 벽을 순회하면서 인접한 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만을 대상으로 탐색을 지속한다.

 

 

그나마 깔끔하게 정리해봤다.

 

이렇게 보고 나니 쉽네..?