[백준] 2589번 보물섬

사용 언어 - Python3, Pypy3

문제 -  2589번 보물섬

DFS (Depth-Frist search, 깊이 우선 탐색) = 경우의 수를 탐색하는 방법. 백트래킹 이용

BFS (Breadth-Frist search, 넓이 우선 탐색) = 노드와 노드의 관계를 탐색하는 방법. 그래프 탐색에 더 좋다.

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

2589번: 보물섬

 

 

정답

BFS 알고리즘을 활용해 그래프 탐색하기

BFS (deque()) = 샛길로 새지 않는다 = 최단 거리

from collections import deque

 

0. 문자열 input

graph = [list(input().rstrip() for _ in range(n)]

 

1.모든 graph 방문하면서 육지인 경우에만 방문

모든 경우의 수에 따라 방문여부/거리 달라지므로 매번 방문여부/거리 초기화 해야한다.

visited

dist

 

2. q = deque()

q.append((y,x)) 첫번째 값 방문

visited[y][x] = 1

 

3. 상하좌우 이동 & 조건 만족

q가 있을 때까지 반복

ey,ex = q.popleft() 현재위치를 q에서 왼쪽값부터 pop한다.

상하좌우로 이동시켜 ny,nx 새로운 위치를 뽑는다.

조건1) ny,nx 가 n*m 안에 있어야함

조건2) 이동하는 위치가 육지여야함 graph[ny][nx] == "L"

조건3) 방문한적이 없어야함 visited[ny][nx] == 0

 

4. 조건 만족시, (ny,nx) 방문한다.

- 방문처리

- dist[ny][nx] 거리는 현재 거리에서 한칸 이동 성공한 것이므로 dist[ey][ex]+1

- dist[ny][nx] 보다 maxi가 작다면 maxi를 계속 큰 값으로 업데이트

- q.append((ny,nx))

 

5. print(maxi)

 

 

6. pypy로 돌려야 시간 초과가 뜨지 않는다.

-> 언어에 따라서 정답여부가 바뀌는 문제는 좋은 문제가 아니다. 코테에선 그럴 일 없음!

from collections import deque

n,m = map(int,input().split()) # 세로, 가로
graph = [list(input().rstrip()) for _ in range(n)] # 문자열

maxi = 0 # 보물 찾기에 가장 긴 시간

# 모든 graph 방문
for y in range(n):
    for x in range(m):
        if graph[y][x] == 'L': # 육지일때만 간다
            # 매번 방문여부/거리 초기화
            visited = [[0 for _ in range(m)] for _ in range(n)]
            dist = [[0 for _ in range(m)] for _ in range(n)]
            
            # BFS
            q = deque()
            q.append((y,x)) # 첫번째 값 방문
            visited[y][x] = 1 # 방문처리
            
            while q:
                ey, ex = q.popleft() # 현재 위치                
                # 4방향 상하좌우 탐색
                for dy, dx in [(1,0),(-1,0),(0,-1),(0,1)]:
                    # 이동 위치
                    ny = ey + dy
                    nx = ex + dx
                    # x와 y안에 있는지 & 육지인지 & 방문하지 않았는지
                    if 0 <= ny < n and 0 <= nx < m and graph[ny][nx] == "L" and visited[ny][nx] == 0:                         
                        visited[ny][nx] = 1 # 방문처리
                        # 현재까지의 거리 + 한 칸 추가, 새로운 값 중 큰 값으로 저장
                        dist[ny][nx] = max(dist[ey][ex]+1, dist[ny][nx])
                        if maxi < dist[ny][nx]: # maxi는 계속 최대값으로 업데이트
                            maxi = dist[ny][nx]
                        q.append((ny,nx)) # 새로운 위치로 방문
                                
print(maxi)

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/2589_%EB%B3%B4%EB%AC%BC%EC%84%AC.py

 

 

 

• DFS VS BFS

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

DFS, BFS의 설명, 차이점