Treasure Island

문제 복기

• 알고리즘 생각 1. 일단 (0,0)에서 시작하여 (r,c)까지 순회하는 BFS를 구현하여 d배열 중 가장 큰값을 리턴하도록 만든다. 2. 1에서 발전시키기 - main : 1에서 시작점을 (0,0)으로 고정하는 것이 아니라 (0,0) ~(r,c) 사이 모든 좌표가 시작점이 되도록 이중 for문으로 구현한다. - bfs 함수 : 거리값을 저장하는 배열 d도 bfs 내에서 초기화한다. 새로운 시작점에 대해 d배열의 최댓값을 새로이 생성하여 리턴한다.

• 코드 최적화 - 실패, 실패원인 분석 2차원 배열 값을 입력받으면서 값이 'L'이면 bfs를 진행하여 정답을 도출하고자 했다. 디버깅 결과 d배열값이 제대로 기록되지 않음을 확인할 수 있었다. 그 이유는 (i,j)값을 입력받고 값이 'L' 을 만족하여 bfs를 순회할지라도, (i+1,j+1) ~(r-1,c-1) 입력값은 미지의 값이기 때문에 bfs 내에서 상하좌우 탐색 및 값 세팅하는 데에 조건을 만족하지 않기 때문에 d배열 값이 제대로 기록되지 않기 때문이다!!!!

따라서 이 방법으로 코드 최적화를 할 순 없다. 2차원 배열값을 다 입력받은 후에 bfs를 실행하고, 정답을 도출해야 한다!

(0,1)에서 시작하는 bfs 실행 후 d배열 값

import java.util.*;
class TI{
	int x, y;
	TI(int x,int y){
		this.x = x;this.y = y;
	}
}
public class TreasureIsland {
	public static int r;
	public static int c;
	public static char[][] a;
	public static int[][] d;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int bfs(int x,int y) {//(0,1)
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				d[i][j] = -1;
			}
		}
		int ans = -1;
		Queue<TI> q = new LinkedList<TI>();
		q.add(new TI(x,y));//(0,1)추가.
		d[x][y] = 0;//시작좌표 d[x][y] = d[0][1] = 0.
		while(!q.isEmpty()) {
			TI cur = q.remove();
			for(int i=0;i<4;i++) {
				int nx = cur.x+dx[i];
				int ny = cur.y+dy[i];
				if(nx<0 || nx>r-1 || ny<0 || ny>c-1) continue;
				if(a[nx][ny] == 'L' && d[nx][ny]==-1) {
					q.add(new TI(nx,ny));
					d[nx][ny] = d[cur.x][cur.y]+1;
				}
			}
		}
		for(int i=0;i<r;i++) {//디버깅용 d출력.
			for(int j=0;j<c;j++) {
				System.out.printf("%3d",d[i][j]);
			}
			System.out.println();
		}
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				if(ans == -1||ans<d[i][j]) {ans = d[i][j];}
			}
		}
		System.out.println("ans  : "+ans);
		return ans;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		r = sc.nextInt();
		c = sc.nextInt();
		a = new char[r][c];
		d = new int[r][c];
		sc.nextLine();
		int res = -1;
		for(int i=0;i<r;i++) {
			String s = sc.nextLine();
			for(int j=0;j<c;j++) {
				a[i][j] = s.charAt(j);
				if(a[i][j]=='L') {//(0,1)
					if(res == -1 || res<bfs(i,j)) {
						res = bfs(i,j);
					}
				}
			}
		}
		//System.out.println();
		System.out.println(res);
	}

}