글 읽기 - 시간초과가 발생했는데 접근이 잘못된거겠죠...?

svolts 2년 전 0

다른 방법이 떠오르지가 않습니다...고수님들 도움 부탁드립니다!!

import sys
from collections import deque

input=sys.stdin.readline

def bfs(start,map):
    dx,dy=[-1,1,0,0],[0,0,-1,1]

    queue=deque([start])
    map[start[0]][start[1]]=1

    while queue:
        x,y=queue.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M and graph[nx][ny]=='.' and map[nx][ny]==0:
                map[nx][ny]=map[x][y]+1
                queue.append((nx,ny))


N,M=map(int,input().split())

graph=[list(input()) for _ in range(N)]

visited=[[0]*M for _ in range(N)]
Visited=[List[:] for List in visited]

Start=[]

for i in [0,N-1]:
    for j in range(M):
        if graph[i][j]=='.':
            Start.append((i,j))

for i in range(1,N-1):
    for j in [0,M-1]:
        if graph[i][j]=='.':
            Start.append((i,j))

bfs(Start[0],visited)
bfs(Start[1],Visited)

Sum=1+max(map(max,visited))

Str=''

for i in range(N):
    for j in range(M):
        if visited[i][j]+Visited[i][j]!=Sum and graph[i][j]=='.':
            graph[i][j]='@'
        Str+=graph[i][j]
    Str+='\n'

print(Str)

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

문제

문제

출처

ICPC

시간초과가 발생했는데 접근이 잘못된거겠죠...?

svolts 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말