글 읽기 - 두 코드의 차이를 모르겠습니다.

wockd9600 1년 전 0

왜 아래 코드만 시간 초과가 발생하는지 모르겠습니다.

# --------------시간초과 x-------------------
from collections import deque
 
# 지도 안에서 활동
def in_range(x, y):
    return -1 < x < n and -1 < y < m
 
def bfs(a, b):
    queue = deque()
    visited = [[0] * m for i in range(n)]
    di = [-1, 1, 0, 0]
    dj = [0, 0, -1, 1]
 
    queue.append([a, b])
    visited[a][b] = 1
 
    # 끝날 때 한번 더 더해주므로 시작은 -1로 한다.
    d = -1
    while queue:
        size = len(queue)
        for _ in range(size):
            a, b = queue.popleft()
            for i in range(4):
                x = a + di[i]
                y = b + dj[i]
                if not in_range(x, y) or visited[x][y] or g[x][y] == "W":
                    continue
                visited[x][y] = 1
                queue.append([x, y])
        d += 1
 
    return d
 
# 입력 받기
n, m = map(int, input().split())
g = [input() for i in range(n)]
 
# 모든 "L"에 대해서 BFS 실행 후 가장 깊이가 큰 것을 찾기
ans = 0
for i in range(n):
    for j in range(m):
        if g[i][j] == "L":
            # 정답 갱신
            ans = max(ans, bfs(i, j))
print(ans)



# --------------시간초과 o-------------------
from collections import deque

def in_range(x, y):
    return -1 < x < n and -1 < y < m

def bfs(x, y):
    queue = deque([(x, y)])
    visited = [[0] * m for _ in range(n)]

    c = -1
    while queue:
        size = len(queue)
        for _ in range(size):
            x, y = queue.popleft()
            visited[x][y] = 1

            for dx, dy in dmove:
                tx, ty = x + dx, y + dy

                if not in_range(tx, ty) or maps[tx][ty] == 'W' or visited[tx][ty]: continue

                queue.append((tx, ty))

        c += 1

    return c

n, m = map(int, input().split())
maps = [input() for _ in range(n)]
dmove = [(1, 0), (0, 1), (-1, 0), (0, -1)]

answer = 0
for i in range(n):
    for j in range(m):
        if maps[i][j] == 'W': continue

        answer = max(answer, bfs(i, j))

print(answer)

wockd9600 1년 전 0

자답입니다.

두 번째 코드는 방문처리를 바로 안 해서 다른 경로와 중복됩니다. (64번째줄)

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

문제

문제

출처

ICPC

두 코드의 차이를 모르겠습니다.

wockd9600 1년 전 0

wockd9600 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말