[BOJ]16946. 벽 부수고 이동하기 4

16946. 벽 부수고 이동하기 4

❌code 1

import sys
from collections import deque


def bfs(r, c):
    dr = [-1, 1, 0, 0]  # 상하좌우
    dc = [0, 0, -1, 1]  # 상하좌우

    q = deque()
    q.append([r, c])  # 시작 지점 추가

    walls = set()  # 주위 벽의 좌표 저장

    cnt = 1  # 이동할 수 있는 칸의 개수
    while q:
        now_r, now_c = q.popleft()
        for d in range(4):
            nr, nc = now_r + dr[d], now_c + dc[d]
            if nr < 0 or R <= nr or nc < 0 or C <= nc:
                continue
            if visited[nr][nc]:
                continue

            # 벽을 만난 경우 벽의 좌표를 저장
            if matrix[nr][nc]:
                walls.add((nr, nc))
                continue

            visited[nr][nc] = 1
            cnt += 1
            q.append([nr, nc])

    # 만난 모든 벽에 대하여 이동 가능한 칸의 개수를 추가
    for wall_r, wall_c in list(walls):
        matrix[wall_r][wall_c] += cnt
        matrix[wall_r][wall_c] = matrix[wall_r][wall_c] % 10


R, C = map(int, input().split())
matrix = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(R)]
visited = [[0] * C for _ in range(R)]  # 이동한 지점을 표시
for row in range(R):
    for col in range(C):
        if matrix[row][col] == 0 and visited[row][col] == 0:
            visited[row][col] = 1  # 출발 지점 표시
            bfs(row, col)

for row in range(R):
    print(''.join(map(str, matrix[row])))

시도

원하는 값을 matrix에 저장하여 이를 출력한다. 이때 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다. 이를 위해 벽의 좌표에 이동 가능한 칸의 개수를 추가하며 계속 10으로 나눈 나머지를 갱신해 주었다.

    # 만난 모든 벽에 대하여 이동 가능한 칸의 개수를 추가
    for wall_r, wall_c in list(walls):
        matrix[wall_r][wall_c] += cnt
        matrix[wall_r][wall_c] = matrix[wall_r][wall_c] % 10

문제

틀린 결과 반환

⭕code 2

import sys
from collections import deque


def bfs(r, c):
    dr = [-1, 1, 0, 0]  # 상하좌우
    dc = [0, 0, -1, 1]  # 상하좌우

    q = deque()
    q.append([r, c])  # 시작 지점 추가

    walls = set()  # 주위 벽의 좌표 저장

    cnt = 1  # 이동할 수 있는 칸의 개수
    while q:
        now_r, now_c = q.popleft()
        for d in range(4):
            nr, nc = now_r + dr[d], now_c + dc[d]
            if nr < 0 or R <= nr or nc < 0 or C <= nc:
                continue
            if visited[nr][nc]:
                continue

            # 벽을 만난 경우 벽의 좌표를 저장
            if matrix[nr][nc]:
                walls.add((nr, nc))
                continue

            visited[nr][nc] = 1
            cnt += 1
            q.append([nr, nc])

    # 만난 모든 벽에 대하여 이동 가능한 칸의 개수를 추가
    for wall_r, wall_c in list(walls):
        matrix[wall_r][wall_c] += cnt


R, C = map(int, input().split())
matrix = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(R)]
visited = [[0] * C for _ in range(R)]  # 이동한 지점을 표시
for row in range(R):
    for col in range(C):
        if matrix[row][col] == 0 and visited[row][col] == 0:
            visited[row][col] = 1  # 출발 지점 표시
            bfs(row, col)

for row in range(R):
    for col in range(C):
        print(matrix[row][col] % 10, end='')
    print()

시도

틀릴만한 부분이 보이지 않아 이동할 수 있는 칸의 개수를 계속 10의 나머지로 갱신하는 대신 출력 과정을 수정하여 통과하였다.

어차피 (x + y + z + ...) % 10의 계산을 하나 (x % 10) + (y % 10) + (z % 10) + ...의 계산을 하나 동일하리라 생각했는데 아래 반례에서 문제를 발견하였다.

8 20
11010100001101010000
01110101010101010101
01110010101010010010
00100101000010010101
01101101100101010110
00000001000010101010
01101101101011101010
00000000000101010110

# code 1의 결과
04030000000000000000
00600000000000000900
00800000000000000000
00000000000000000108
00000000000000000170
00000000000000001070
00000000000000202070
00000000000000030450

# code 2의 결과
02010600008300080000
00200608070300080102
00100070701090080030
00000001000080080207
00000000000100000360
00000000000020105070
00000000000012406070
00000000000103050450

문제 해결

결과적으로 나눗셈에 문제가 있는 것은 아니었다. code 1의 경우 matrix[wall_r][wall_c]의 값이 10의 배수가 나온다면 그 값은 0으로 저장될 것이다. 여기서 문제가 생기는데, 이후 다시 while loop가 진행될 때에 0으로 표시된 부분은 아래 코드를 실행할 수 없다. 따라서 틀린 결과를 반환하게 된다.

            # 벽을 만난 경우 벽의 좌표를 저장
            if matrix[nr][nc]:
                walls.add((nr, nc))
                continue

요약

양의 정수를 벽으로 판별하는 코드에서 벽으로 저장된 값을 10의 나머지로 갱신할 시 해당 값은 양의 정수를 벗어난 값 즉, 0을 가질 수 있게 된다. 따라서 양의 정수 값은 벽이라는 가정이 깨지게 되어 오류가 발생하게 된다.