백준 2589 보물섬

백준 2589 보물섬

1. 문제 링크

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

2589번: 보물섬

 

2. 문제 해결에 대한 아이디어

1. 결국 가장 멀리 떨어진 지점의 이동시간을 구하는 문제이다.

2. 지도가 공백 문자 없이 문자열로 들어오기 때문에 문자열로 받은 후 .charAt(index) 를 사용하여 배열을 구성한다.

3. 이차원 배열을 순회하면서 'L'일 때 방문할 수 있는 모든 곳을 방문하며 가중치(weight)를 기록한다.

4. 한 지점으로부터의 방문이 끝나면 최대가중치를 갱신한다.

5. 한 지점에 대한 방문작업이 끝나면 가중치를 기록하는 배열을 초기화한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static char[][] board;
	static int[][] visit; // 가중치를 기록하기 위해 int 배열로 선언
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static int Y, X;
	static int maxCnt = 0; // 가장 멀리 떨어진 거리

	// L 육지 W 바다
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] yx = br.readLine().split(" ");
		Y = Integer.parseInt(yx[0]);
		X = Integer.parseInt(yx[1]);

		board = new char[Y][X];
		visit = new int[Y][X];

		for (int i = 0; i < Y; i++) {
			String line = br.readLine();
			for (int j = 0; j < X; j++) {
				board[i][j] = line.charAt(j);
			}
		}

		for (int i = 0; i < Y; i++) {
			for (int j = 0; j < X; j++) {
				if (board[i][j] == 'L' && visit[i][j] == 0) {
					BFS(i, j);
					visit = new int[Y][X];
				}
			}
		}

		System.out.println(maxCnt);

	}

	static void BFS(int i, int j) {
		int cnt = 0;
		Queue<Loc> q = new LinkedList<>();
		q.add(new Loc(i, j));

		visit[i][j] = 1; // 시작 위치의 가중치를 1로 잡음

		while (!q.isEmpty()) {
			Loc now = q.poll();
			int y = now.y;
			int x = now.x;

			for (int d = 0; d < 4; d++) {
				int yy = y + dirY[d];
				int xx = x + dirX[d];
				if (yy < 0 || xx < 0 || yy >= Y || xx >= X || 
						visit[yy][xx] != 0 || board[yy][xx] == 'W')
					continue;
				visit[yy][xx] = visit[y][x] + 1;
				cnt = Math.max(cnt, visit[yy][xx]);
				q.add(new Loc(yy, xx));
			}
		}

		maxCnt = Math.max(cnt - 1, maxCnt); // 초기 셋팅을 1로 잡았으므로 다시 1을 빼준다
	}
}

class Loc {
	int y, x;

	public Loc(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 가장 멀리 떨어진 지점과 최단거리라는 단어가 동시에 사용되면서 헷갈릴 뻔했다.

2. 공백 문자 없이 들어오는 인풋 값 처리하는 방법을 잘 숙지해야겠다. --> .chatAt(index)