글 읽기 - 문제 해결 방안 + 코드

kbiglight 3년 전 0

이 문제를 풀기 위해 bfs를 고려했습니다. 먼저 입력을 받을때 1인 경우 좌표를 queue에 먼저 넣어놓고

이 큐를 통해 bfs를 진행하며 +1을 해주면서 맵을 채워가는 방식을 채택했습니다.

그리고 맵에 0이 남아 있다면 0을 출력하게

없다면 max값을 출력하게 코드를 짰습니다.

혹시 이렇게 풀면 어디서 논리적 오류가 발생할까요...? ㅠㅠ

밑은 그를 토대로 구현한 코드입니다

import sys
from collections import deque
from pprint import pprint as pp

input: () = lambda: sys.stdin.readline().strip()
sys.stdin = open('inputs/boj/7576_input')


def solution(graph, queue):
    dir = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    # 혹시 모를 visited 행렬 구현
    visited = [[0 for _ in range(m)] for _ in range(n)]

    while queue:
        r, c = queue.popleft()
        for dr, dc in dir:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < m and graph[nr][nc] == 0:
                graph[nr][nc] = graph[r][c] + 1
                visited[nr][nc] = visited[r][c] + 1
                queue.append(tuple([nr, nc]))

    if 0 in graph:
        return -1
    else:
        return max(max(visited))


if __name__ == '__main__':
    m, n = map(int, input().split())
    farm = []
    queue = deque()
    for i in range(n):
        line = list(map(int, input().split()))
        for j in range(m):
            if line[j] == 1:
                # 1인 경우에 큐에 넣어준다.
                queue.append(tuple([i, j]))

        farm.append(line)

    result = solution(farm, queue)
    print(result)

shg9411 3년 전 1

max(max(visited))를 한다고 원하는 결과가 나오시진 않을 것 같습니다.

만약 visited가 [[5,1],[1,6]]라면

원하는 값은 6이겠지만, 출력 값은 5가 나오지 않을까요?

shg9411 3년 전 1

0 in graph도 비슷한 이유로 원하시는데로 작동하지 않을 것 같은데요.

kbiglight 3년 전 0

@shg9411

일단 예시 코드들은 다 정상 작동 되던데....

1 -1

-1 1도 정상적으로 0이 나옵니다....2번 예시도 정상적으로 -1이 나오고...

kbiglight 3년 전 0

테스트 해보니까.... shg9411 님의 말씀이 맞네요....

max(max()) 부분에서 문제가 발생하네요.... 감사합니다 ㅠㅠ

kbiglight 3년 전 0

6 5
0 0 1 0 0 0
0 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0

가 좋은 반례가 되었습니다 언제나 도움주셔서 감사합니다 (_ _)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제 해결 방안 + 코드

kbiglight 3년 전 0

shg9411 3년 전 1

shg9411 3년 전 1

kbiglight 3년 전 0

kbiglight 3년 전 0

kbiglight 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말