[백준] 2589번 : 보물섬 - 자바(JAVA)

 

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

2589번: 보물섬

 

문제 해석

직사각형 모양을 가진 보물섬 지도가 존재한다.

지도는 여러 칸으로 나뉘어 있으며 각 칸은 육지(L)나 바다(W)로 표시되어 있다.

지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는 데 한 시간이 걸린다.

보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하라.

---

입력

첫째줄에는 보물 지도의 세로의 크기와 가로의 크기가 주어진다.

둘째줄부터는 L과 W로 표시된 보물 지도가 주어진다.

 

제약조건

가로, 세로의 크기는 각각 50 이하이다.

---

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

---

문제 풀이 전 설계

입력받기

첫째 줄에 세로의 크기와 가로의 크기를 빈칸 사이에 두고 입력받는다.

세로의 크기와 가로의 크기를 기반으로 반복문을 통해 W, L을 입력받는다.

효율적인 입출력을 위해 BufferedReader, StringTokenizer, BufferedWriter를 사용합니다.

 

핵심 기능

최단 거리가 가장 먼 곳을 찾아야 한다. ( BFS사용)

visited 배열이 모두 true가 될 때까지 재귀 호출한다.

육지로만 이동할 수 있다. ( visited 배열 초기화할 때 L은 false, W는 true)

---

풀이하면서 고민한 점

만약에 보물의 시작 지점과 끝 지점의 좌표를 안다면 시작 지점부터 BFS를 시작하여 끝 지점까지 도달하기까지 걸린 이동 수를 반환하게 된다면 보물이 묻혀 있는 두 곳 사이를 최단 거리로 반환할 수 있습니다.

 

하지만 우리는 보물이 어디에 숨겨진 지도 알지 못합니다.

 

그러면 보물의 위치를 어떻게 찾아야 할까요

 

보물을 탐색하기 위해 반복문을 통해 탐색한다고 생각해 보겠습니다.

위의 그림에서 검은색 부분이 보물의 위치인데 보물의 탐색과정을 살펴보겠습니다

for(int i=0; i< height; i++){
	for(int j= 0; j< width; j++){
		if(treasureBoard[i][j] == 'L'){
        		//보물 좌표 찾는 로직
        }    	
    }
}

위의 반복문을 사용하여 만약 보드의 값이 육지(L)이라면 순차적으로 보물의 좌표를 탐색합니다.

(0, 1) 시작

1. (0,1)을 어떤 자료구조에 넣고 상하좌우로 이동할 수 있는지 탐색합니다.

2. 아래, 오른쪽으로 이동이 가능하므로 아래(1,1), 오른쪽 좌표(0,2)를 자료구조에 넣고 (0,1)을 삭제합니다.

3. 자료구조에 존재하던 2개의 값이 상하좌우 어디로 이동할 수 있는지 탐색합니다. (1,1)은 왼쪽 오른쪽으로 이동 가능합니다. 위쪽은 아까 방문했던 곳이기 때문에 방문할 수 없음!

4.  (1,1)이 갈 수 있는 좌표를 자료구조에 넣고 (0,2)의 좌표도 똑같이 검사하는 것을 반복합니다.

5. 만약 어떤 좌표가 더 이상 이동할 수 없다면 해당 좌표값이 기록됩니다.

 

그렇게 모두 담은 좌표값을 비교하고 싶었지만 그러기 위해서는 왼쪽 육지와 오른쪽 육지를 구분지어야 합니다..

 

포기하려고 했지만 다시 생각해보니 사실 보물의 위치를 알 필요가 없습니다.

우리가 출력해야 하는 것은 최단 거리가 가장 먼 곳을 찾아야 하기 때문입니다.

육지(L) 기준으로 BFS단계를 거칠 때마다 count를 하고 만약에 더 이상 이동하지 못하면 return 합니다.

그렇게 되면 해당 위치에서 최단거리가 가장 먼 거리를 알 수 있기 때문에 반복문을 통해 육지마다 가장 먼 거리를 측정하고 그중 최댓값을 구한다면 출력 값이 될 것입니다.

 

너무 어렵게 생각한 것 같고 단순한 BFS문제 같습니다.

 

BFS를 구현할 때 자료구조를 어떤 것을 사용해야 할까요?

우선 BFS가 어떻게 동작하는지부터 살펴보겠습니다.

1. 자료구조에 좌표값을 넣습니다. (2, 2, 0)라고 가정 0은 depth

while (자료구조가 비어있을때 까지 반복){
	2. 거리를 구하기 위한 Depth를 1 증가시킵니다.
	3. 자료구조에 가장 최근에 들어간 값을 꺼냅니다.
	4. 꺼내며 이 좌표를 기준으로 상하좌우 이동할 수 있는 좌표를 자료구조에 추가합니다.
}

 

처음에는 ArrayList를 사용하려고 했습니다.

하지만 ArrayList를 사용하게 되면 맨 앞, 맨뒤에서만 삽입 삭제가 일어나기 때문에 index가 밀리는 연산이 발생하게 됩니다.

따라서 LinkedList를 사용하며 선입선출 구조를 가지는 자료구조인 Queue를 사용합니다.

Queue

문제를 해결하던 도중 BFS를 할때마다 count를 했기 때문에 돌아가는 길이 발생하는 경우에 잘못된 답이 출력되었습니다. 따라서 이를 해결하기 위해서 어떻게 해야 할지 몰랐는데 depth, cost를 적용하게된다면 이 값이 최대값인 경우가 최단거리라는것을 알게 되었습니다.

depth

 

(y좌표, x좌표, depth)라는 int[] name = new int[3]; 을 사용하는것보다 Point 클래스를 만들어서 사용한다.

---

어려웠던 점

좌표의 i, j 값을 자꾸 가로 세로로 생각하는 경향이 있어서 헷갈렸습니다.

또한 배열의 인덱스 범위지정을 tempI >=0 으로 설정해야 하는데 temp >0 으로 설정하는 작은 실수들이 있었다.

초기 들어간 좌표에 visited[][] = false로 설정하지 않았었다.

처음에 BFS를 할때마다 count를 했기 때문에 돌아가는 길에도 count가 증가되어 잘못된 답이 출력되었습니다.

큐의 요소마다 depth를 적용해서 최대 depth를 출력해야 돌아가는 경우를 막을 수 있습니다.

---

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/*
   	BOJ : 2589번 보물섬
  	직사각형 모양을 가진 보물섬 지도가 존재한다.
	지도는 여러 칸으로 나뉘어 있으며 각 칸은 육지(L)나 바다(W)로 표시되어 있다.
	지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는 데 한 시간이 걸린다.
	보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.
	보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하라.
 */
class Point {
	int x;
	int y;
	int depth;

	// i,j 값을 넣게 되면 좌표계상으로는 y,x값이기 때문에 y,x 순서로 생성자를 만들었습니다.
	public Point(int y, int x, int depth) {
		this.x = x;
		this.y = y;
		this.depth = depth;
	}
}

public class TreasureIsland {
	static char[][] treasureBoard;
	static boolean[][] visited;
	static int maxDistance = 0;
	static int height;
	static int width;
	// 상좌우하
	static int[] dy = { -1, 0, 0, 1 };
	static int[] dx = { 0, -1, 1, 0 };
	static Queue<Point> coordQ = new LinkedList<Point>();

	public static void main(String[] args) throws IOException {
		initialize();
		searchTreasureDistance();
		printMaxDistance();
	}

	static void initialize() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		height = Integer.parseInt(st.nextToken());
		width = Integer.parseInt(st.nextToken());
		treasureBoard = new char[height][width];
		visited = new boolean[height][width];

		for (int i = 0; i < height; i++) {
			String temp = new StringTokenizer(br.readLine()).nextToken();
			for (int j = 0; j < width; j++) {
				char tempChar = temp.charAt(j);
				treasureBoard[i][j] = tempChar;
				if (tempChar == 'L') {
					visited[i][j] = true;
				}
			}
		}
		br.close();

	}

	static void initializeTest() {

		for (int i = 0; i < treasureBoard.length; i++) {
			for (int j = 0; j < treasureBoard[i].length; j++) {
				System.out.print(treasureBoard[i][j] + " ");
			}
			System.out.println();
		}

		for (int i = 0; i < visited.length; i++) {
			for (int j = 0; j < visited[i].length; j++) {
				System.out.print(visited[i][j] + " ");
			}
			System.out.println();
		}
	}

	static void searchTreasureDistance() {
		for (int i = 0; i < treasureBoard.length; i++) {
			for (int j = 0; j < treasureBoard[i].length; j++) {
				if (!(treasureBoard[i][j] == 'L')) {
					continue;
				}
				addCoordToQueue(i, j, 0);
				changeVisitedByCoord(i, j);
				BFS();
				queueClear();
				resetVisited();

			}
		}
	}

	static void addCoordToQueue(int i, int j, int depth) {
		Point tempP = new Point(i, j, depth);
		coordQ.add(tempP);

	}

	static void changeVisitedByCoord(int i, int j) {
		visited[i][j] = false;
	}

	static void BFS() {				
		while (!coordQ.isEmpty()) {
			Point tempP = coordQ.poll();
			for (int k = 0; k < 4; k++) {
				int tempI = tempP.y + dy[k];
				int tempJ = tempP.x + dx[k];
				if (!isGo(tempI, tempJ)) {
					continue;
				}
				int depth = tempP.depth+1;
				visited[tempI][tempJ] = false;
				addCoordToQueue(tempI, tempJ, depth);
				maxDistance = maxDistance > depth ? maxDistance : depth;
			}
		}
	}

	static boolean isGo(int tempI, int tempJ) {		
		return (tempI >= 0) && (tempJ >= 0) && (tempJ < width) && (tempI < height) && (visited[tempI][tempJ] == true);	
	}

	static void queueClear() {
		coordQ.clear();
	}

	static void resetVisited() {
		for (int i = 0; i < treasureBoard.length; i++) {
			for (int j = 0; j < treasureBoard[i].length; j++) {
				if (treasureBoard[i][j] == 'L') {
					visited[i][j] = true;
				}
			}
		}
	}

	static void printMaxDistance() throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(maxDistance + "\n");
		bw.flush();
		bw.close();
	}

}