[파이썬] 백준 알고리즘 2589번: 보물섬 문제풀이 BFS

문제

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

백준 2589 문제

백준2589번 입출력

이러한 문제이다.

아이디어

우선 graph[][]와 visited[][] 의 2차원 리스트를 입력받은 다음

다음과 같이

visited[][]에 이전값을 기억하면서 최대 이동거리를 잰다음 반복문을 돌때마다 가장 큰 값을 출력하는 아이디어를 내고 소스코드를 짰다.

 

잘못된 소스코드

"""
1. 아이디어
  - L인 곳을 반복문으로 구하고, bfs알고리즘을 수행하며 visited 값에 1씩 추가해가며 visited 배열을 최신화해간다.
  - 반복문 마지막 라인에 리턴 값의 가장 큰 값을 저장한다.
2. 시간복잡도
    - 반복문 n*m = * bfs(v+e) = 50*50*50*50 =6250000 < 1억 (가능)
3. 자료구조
    - visited = bool[n][m]
    - graph = str[n][m]
    - res = int
"""

from collections import deque
n, m = map(int, input().split())

graph = []

for k in range(n):
    graph.append(list(input()))

res = 0

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

def bfs(y, x):
    cnt = 0
    visited[y][x] = 0
    q = deque()
    q.append((y,x))

    while q:
        (y, x) = q.popleft()
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if (0<=ny<n) and (0<=nx<m):
                if graph[ny][nx] == "L" and not visited[ny][nx]:
                    q.append((ny, nx))
                    visited[ny][nx] = visited[y][x] + 1
                    cnt = visited[y][x] + 1
    return cnt

for y in range(n):
    for x in range(m):
        if graph[y][x] == "L":
            visited = [[False] * m for _ in range(n)]
            res = max(bfs(y,x), res)

print(res)

 

이렇게 짰더니 55%에서 틀렸다고 떴다. 도저히 이유를 찾을수가 없어서 질문게시판에서 반례를 받았는데

2 2
LL
WW

answer : 1
output : 2

 

이런 반례가 있었다. 왜 이렇게 나오는지 소스코드를 확인해보니

초기값이 0이기 때문에 방문을 하지 않았다고 not visited[y][x]가 참이 되어서 한번 더 수행하여 2가 나온것이였다.

코드를 다시 짜야하나 고민하고 있다가 True는 1로 취급하니깐 visited[y][x] = 0 -> True로 시작하고 return cnt -> return cnt-1를 해주면 올바르게 방문여부를 판단했다.

 

그래서 바뀐 소스코드는 이렇다

수정한 소스코드

"""
1. 아이디어
  - L인 곳을 반복문으로 구하고, bfs알고리즘을 수행하며 visited 값에 1씩 추가해가며 visited 배열을 최신화해간다.
  - 반복문 마지막 라인에 리턴 값의 가장 큰 값을 저장한다.
2. 시간복잡도
    - 반복문 n*m = * bfs(v+e) = 50*50*50*50 =6250000 < 1억 (가능)
3. 자료구조
    - visited = bool[n][m]
    - graph = str[n][m]
    - res = int
"""

from collections import deque
n, m = map(int, input().split())

graph = []

for k in range(n):
    graph.append(list(input()))

res = 0

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

def bfs(y, x):
    cnt = 0
    visited[y][x] = True # 바뀐 부분
    q = deque()
    q.append((y,x))

    while q:
        (y, x) = q.popleft()
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if (0<=ny<n) and (0<=nx<m):
                if graph[ny][nx] == "L" and not visited[ny][nx]:
                    q.append((ny, nx))
                    visited[ny][nx] = visited[y][x] + 1
                    cnt = visited[y][x] + 1
    return cnt-1 # 바뀐 부분

for y in range(n):
    for x in range(m):
        if graph[y][x] == "L":
            visited = [[False] * m for _ in range(n)]
            res = max(bfs(y,x), res)

print(res)

 

이렇게 작성하니 정답이였다.

 

배운것

길이를 저장하기 위해 그래프에 저장할 때 0으로 저장하면 False로 인식해 올바르지 않은 결과가 나오는 것을 알았다.

다음부터 이런 문제가 나오면 visited[][] = True로 해두고 결과에 -1을 해주면 올바른 결과가 나올것이라고 생각이 들었다.