[BOJ-2589] 보물섬

https://www.acmicpc.net/problem/2589

2589번: 보물섬

---

[풀이]

전형적인 bfs문제이긴한데

방문체크를 해놓는다.

---

[코드1] Python3로하면 시간초과/ PyPy3로하면 통과(155584KB, 852ms)

import sys
from collections import deque
input=sys.stdin.readline
q=deque()

N, M= map(int, input().split())
MAP=[   [*input().strip()] for _ in range(N)]

dy=(-1,1,0,0)
dx=(0,0,-1,1)

def isRange(y,x):
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs(y,x,cnt):
    max_dist=0
    visited=[[False]*M for _ in range(N)]
    q.append((y,x,cnt))
    while q:
        y,x, cnt=q.popleft()
        if not visited[y][x]:
            visited[y][x]=True
            
            if max_dist<cnt:
                max_dist=cnt
            for i in range(4):
                nexty=y+dy[i]
                nextx=x+dx[i]
                if isRange(nexty, nextx):
                    if (not visited[nexty][nextx]) and (MAP[nexty][nextx]=='L'):
                        q.append((nexty, nextx, cnt+1))
    return max_dist #멀리떨어진 거리 리턴 
        
result=0
for y in range(N):
    for x in range(M):
        if MAP[y][x]=='L':
            result=max(result, bfs(y,x,0))
print(result)

 

[코드2] 720ms /PyPy3 통과

import sys
from collections import deque
input=sys.stdin.readline
q=deque()

N, M= map(int, input().split())
MAP=[[*input().strip()] for _ in range(N)]

dy=(-1,1,0,0)
dx=(0,0,-1,1)

def isRange(y,x):
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs(y,x,cnt):
    max_dist=0
    visited=[[False]*M for _ in range(N)]
    visited[y][x]=True #처음위치 방문
    q.append((y,x,cnt))
    
    while q:
        y,x, cnt=q.popleft()
        if max_dist<cnt:
            max_dist=cnt
        for i in range(4):
            nexty=y+dy[i]
            nextx=x+dx[i]
            if isRange(nexty, nextx):
                if (not visited[nexty][nextx]) and (MAP[nexty][nextx]=='L'):
                    q.append((nexty, nextx,cnt+1))
                    visited[nexty][nextx]=True #다음위치 미리방문
    return max_dist
        
result=0
for y in range(N):
    for x in range(M):
        if MAP[y][x]=='L':
            result=max(result, bfs(y,x,0))
print(result)

 

 

[코드3] 784ms /PyPy3

dist[y][x] 를 이용하여 거리계산

import sys
from collections import deque
input=sys.stdin.readline
q=deque()

N, M= map(int, input().split())
MAP=[[*input().strip()] for _ in range(N)]


dy=(-1,1,0,0)
dx=(0,0,-1,1)

def isRange(y,x):
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs(y,x):
    visited=[[False]*M for _ in range(N)]
    dist=[[0]*M for _ in range(N)]
    max_distance=0
    q.append((y,x))
    visited[y][x]=True #처음위치 방문
    
    while q:
        y,x=q.popleft()
        for i in range(4):
            nexty=y+dy[i]
            nextx=x+dx[i]
            if isRange(nexty, nextx):
                if (not visited[nexty][nextx]) and (MAP[nexty][nextx]=='L'):
                    q.append((nexty, nextx))
                    dist[nexty][nextx]=dist[y][x]+1
                    visited[nexty][nextx]=True #다음위치 방문
                    if max_distance<dist[nexty][nextx]:
                        max_distance=dist[nexty][nextx]
                        
    return max_distance #맨마지막 cnt를 리턴. 
        
result=0
for y in range(N):
    for x in range(M):
        if MAP[y][x]=='L':
            result=max(result, bfs(y,x))
print(result)

---

[실패코드]

그냥 전형적인 BFS를 사용했다.

그리고 계속 MAP[y][x]='L'일 때, 방문리스트 visited를 False로 초기화하여

가장 긴 거리를 구했다.(큐에서 마지막으로 빠져나오는 cnt)

 

언어를 Pypy3로 하면.. 메모리초과가 뜨고

Python으로하면 시간초과가 뜨고...@@;

import sys
from collections import deque
input=sys.stdin.readline
q=deque()

N, M= map(int, input().split())
MAP=[[*input().strip()] for _ in range(N)]
max_distance=0

dy=(-1,1,0,0)
dx=(0,0,-1,1)

def isRange(y,x):
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs(y,x,cnt):
    visited=[[False]*M for _ in range(N)]
    q.append((y,x,cnt))
    while q:
        y,x, cnt=q.popleft()
        visited[y][x]=True
        for i in range(4):
            nexty=y+dy[i]
            nextx=x+dx[i]
            if isRange(nexty, nextx):
                if (not visited[nexty][nextx]) and (MAP[nexty][nextx]=='L'):
                    q.append((nexty, nextx, cnt+1))
    return cnt #맨마지막 cnt를 리턴. 
        
result=0
for y in range(N):
    for x in range(M):
        if MAP[y][x]=='L':
            result=max(result, bfs(y,x,0))
print(result)