글 읽기 - 무한 입력...

jaehyeoklim 2년 전 0

무한 입력으로 되네요.. dfs로 섬 구분까진 되는데

그 이후 bfs로 최단 거리 할 때 while문을 못 끝내거나 끝맺음 조건이 없어서 무한 입력 상태가 되는 거 같은ㄷ에

무슨 조건을 더 추가해줘야할 지 모르겠습니다..

import sys
from collections import deque
sys.setrecursionlimit(100000000)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def change():
    global dfs_cnt
    if dfs_cnt + 2 not in dfs_cnt_list:
        dfs_cnt_list.append(dfs_cnt + 2)
    return dfs_cnt + 2

def dfs(x, y):
    world_map[x][y] = change()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx <= -1 or nx >= N or ny <= -1 or ny >= N or world_map[nx][ny] != 1:
            continue
        dfs(nx, ny)

def bfs(x, y, count, x2):
    queue = deque()
    queue.append((x, y, count, x2))
    while queue:
        x, y, count, x2 = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx <= -1 or nx >= N or ny <= -1 or ny >= N:
                continue
            else:
                if world_map[nx][ny] == 0:
                    # count = min(count, bfs(nx, ny, count - 1))
                    # world_map[nx][ny] = world_map[nx][ny] + 1
                    queue.append((nx, ny, count + 1, x2))
                elif world_map[nx][ny] == x2:
                    continue
                # if world_map[nx][ny] != x2 and world_map[nx][ny] != 0:
                else:
                    break
    return count

                
def program(x):
    for i in range(N):
        for j in range(N):
            if world_map[i][j] == x:
                result.append((bfs(i, j, 0, x)))

N = int(input())
world_map, result, dfs_cnt_list, dfs_cnt = [], [], [], 0

for _ in range(N):
    world_map.append(list(map(int, sys.stdin.readline().split())))

for i in range(N):
    for j in range(N):
        if world_map[i][j] == 1:
            dfs(i, j)
            dfs_cnt += 1   

# for i in range(len(world_map)):
#     print(world_map[i])

for i in range(len(dfs_cnt_list)):
    program(dfs_cnt_list[i])
    # print(dfs_cnt_list[i])

# print(result)
# while 0 in result:
#     result.remove(0)
    
print(min(result))

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

문제

문제

출처

ICPC

무한 입력...

jaehyeoklim 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말