백준 2589 보물섬 풀이 python, java

문제로이동

2589번: 보물섬

---

목차

 

---

---

문제 설명

보통 보물의 위치가 정해져 있고 특정 위치에서 해당 보물들을 찾는 문제라면, 이 문제는 그 보물을 직접 찾고 최단거리를 출력해야 합니다. 이 문제를 읽고 나면 아래와 같은 의문점이 생깁니다.

• 보물을 찾는 방법?
• 최단 거리는 어떻게 구할 것인가?
• 같은 좌표인데 거리가 다른경우?
  • 좌표가 같다면 거리가 짧은 것으로 갱신
  • 아예 bfs를 써서 돌리면 최단 거리에서 return되기 때문에 걱정없음

이처럼 여러 가지 의문점이 생겼었는데 정리하자면 이렇습니다.

 

출발점과 도착점은 같지만 이동 거리가 8, 10으로 다르다.

BFS로 탐색을 수행하면 가장 먼저 return 되는 값이 최단거리입니다.

그렇기에 위 그림처럼 길이가 더 긴 거리가 MAX값이 될 일은 없습니다.

 

필드의 width, height 크기만큼 반복문을 수행했고 모든 좌표를 탐색합니다.

(물론 값 입력 시에 L 필드의 좌표만 따로 저장해두셨다가 돌리셔도 좋습니다.)

 

L필드를 찾았다면 bfs를 수행합니다.

여기서, bfs에서는 최단거리를 반환합니다.

 

반환된 값이 다른 경로 최단거리보다 크다면 max를 갱신해주고 최종적으로 모든 반복문이 종료되면(모든 L 탐색이 끝나면) max를 출력해 줍니다.

 

Java와 Python의 로직은 동일합니다.

---

소스 코드

Python

from collections import deque
H,W = map(int,input().split())
field = list()
direction = [[0,1],[1,0],[-1,0],[0,-1]]

for _ in range(H):
    field.append(list(input()))
def bfs(rx,ry):
    visited = [[0]*W for _ in range(H)]
    q = deque([[rx,ry]])    
    visited[ry][rx]=1
    maxcnt = 0
    while q:
        x,y = q.popleft()
        for dx,dy in direction:
            nx,ny = dx+x,dy+y
            if 0<=nx<W and 0<=ny<H and field[ny][nx]=='L' and visited[ny][nx]==0:
                visited[ny][nx]=visited[y][x]+1
                if maxcnt < visited[ny][nx]:maxcnt=visited[ny][nx]
                q.append([nx,ny])
    return maxcnt-1
answer = 0
for i in range(H):
    for j in range(W):
        if field[i][j]=='L':
            tmp = bfs(j,i)
            if tmp>answer:
                answer = tmp
print(answer)
                

---

Java8

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static class node{
		int x,y;
		node(int x,int y){
			this.x = x;
			this.y = y;
		}
	}
	static int H,W;
	static char field[][];
	static int dirx[]= {0,1,-1,0};
	static int diry[]= {1,0,0,-1};
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
	static int bfs(int rx, int ry) {
		int visited[][] = new int[H][W];
		visited[ry][rx]=1;
		Deque<node> q = new LinkedList<node>();
		node n = new node(rx,ry);
		q.addLast(n);
		int maxcnt = 0 ;
		while(!q.isEmpty()) {
			node qxy = q.pollFirst();
			for(int i = 0 ; i <4;i++) {
				int nextX = qxy.x + dirx[i];
				int nextY = qxy.y + diry[i];
				if(0<=nextX && nextX<W && 0<=nextY && nextY<H && field[nextY][nextX]=='L' && visited[nextY][nextX]==0) {
					visited[nextY][nextX]=visited[qxy.y][qxy.x]+1;
					if(maxcnt<visited[nextY][nextX])maxcnt=visited[nextY][nextX];
					node nnd = new node(nextX,nextY);
					q.addLast(nnd);
				}
			}
		}
		return maxcnt-1;
	}
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		field = new char[H][W];
		for(int i = 0 ; i < H;i++) {
			st = new StringTokenizer(br.readLine());
			String tmp = st.nextToken();
			for(int j = 0 ; j < W;j++)
				field[i][j] = tmp.charAt(j);
		}
		int max = 0;
		for(int i = 0 ; i < H;i++)
			for(int j = 0 ; j < W; j++) {
				if(field[i][j]=='L') {
					int tmp = bfs(j,i);
					if (max<tmp)max=tmp;
				}	
			}
		System.out.println(max);
	}
}