글 읽기 - 2146번 파이썬으로 시간 더 줄일 수 있을까요?

kimjeongtae 1년 전 0

1. 나라별로 dfs를 통해 1, 2, 3... 번호를 매기면서 사이드 구간을 모두 기록합니다.

2. for문으로 모든 사이드 구간을 돌며 bfs를 통해 다른 나라까지 최소 거리를 기록합니다.

3. 최소 거리를 출력합니다.

정답이긴 했지만 약 6초가 나와서 더 효율적으로 풀 수 있을까 질문드립니다.

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

def dfs(i, j):
    lst[i][j] = now
    visited[i][j] = 1
    row = [-1, 0, 0, 1]
    col = [0, -1, 1, 0]
    for idx in range(4):
        r = i + row[idx]
        c = j + col[idx]
        if 0 <= r <= n-1 and 0 <= c <= n-1:
            if not visited[r][c]:
                if lst[r][c]:
                    dfs(r, c)
                else:
                    side[-1].add((r, c))

def bfs(i, j):
    queue = deque([(i, j, 1)])
    visited[i][j] = 1
    row = [-1, 0, 0, 1]
    col = [0, -1, 1, 0]
    result = 10**7
    while queue:
        now = queue.popleft()
        for num in range(4):
            r = now[0] + row[num]
            c = now[1] + col[num]
            if 0 <= r <= n-1 and 0 <= c <= n-1:
                if not visited[r][c]:
                    visited[r][c] = 1
                    if not lst[r][c]:
                        queue.append((r, c, now[2]+1))
                    elif lst[r][c] != idx+1 and result > now[2]:
                        result = now[2]
    return result

n = int(sys.stdin.readline())
lst = []
for i in range(n):
    lst.append(list(map(int, sys.stdin.readline().split())))
visited = [[0 for i in range(n)] for j in range(n)]
now = 1
side = []
for i in range(n):
    for j in range(n):
        if not visited[i][j] and lst[i][j]:
            side.append(set())
            dfs(i, j)
            now += 1
result = 10**7
for idx in range(len(side)):
    for i,j in side[idx]:
        visited = [[0 for i in range(n)] for j in range(n)]
        distance = bfs(i, j)
        if result > distance:
            result = distance
print(result)

jeno8522 1년 전 0

36 elif lst[r][c] != idx+1 and result > now[2]:

37 result = now[2]

이부분을 굳이 쓰지말고 해당 조건을 충족하면 now[2]가 최소 거리 일테니 바로 return 때리면 더 빠르지 않을까요

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

문제

문제

출처

ICPC

2146번 파이썬으로 시간 더 줄일 수 있을까요?

kimjeongtae 1년 전 0

jeno8522 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말