Heart’s Develop Inside

package practice;
 
import java.io.*;
import java.util.*;
 
/**
 * 미로를 탈출하는 데, 출발 지점에서 도착 지점까지 최소한의 벽만 깨고 도달하는 것이 목적.
 
 * 출발 지점 -> 도착 지점까지 깨야 하는 벽의 최소 갯수를 구하라
 
 * 
 
 * Input 파일의 내용
 
 * 첫 라인 : 행 열
 
 * 2~(행+1) 라인 : 열 만큼의 s | . | # | e
 
 * s가 시작 위치, e 가 끝 위치
 
 * .은 지나갈 수 있는 길, #는 벽
 
 * 
 
 * Input 파일의 내용 예제
 
 * 5 6
 
 * s.#...
 
 * ..####
 
 * #.#..#
 
 * ..###.
 
 * ###..e
 
 * 
 
 * 예제에 대한 답 : 2
 
 */
public class PracticeDijkstra {
	/** 이어지지 않은 거리(무게) */
	public static final int UNTOUCHABLE_DISTANCE = 99;
 
	/** 입력 파일명 */
	public static final String INPUT_FILE_NAME = "input.txt";
 
	/** 미로의 가로 */
	private int width = 0;
 
	/** 미로의 세로 */
	private int height = 0;
 
	/** 미로의 전체 칸 갯수 */
	private int nodeCount = 0;
 
	/** 미로 시작 지점(칸 위치 - 1차원으로 계산) */
	private int startIdx = 0;
 
	/** 미로 끝 지점(칸 위치 - 1차원으로 계산) */
	private int endIdx = 0;
 
	/** 인접 행렬 */
	private int [][] adjacentMatrix = null;
 
	/** 작업된 집합 */
	private ArrayList proceedList = null;
 
	/** 작업 대기 집합 */
	private ArrayList readyList = null;
 
	public PracticeDijkstra() {
		initValues();
	}
 
	private void initValues() {
		// Initialize
		adjacentMatrix = null;
		proceedList = null;
		readyList = null;
 
		width = 0;
		height = 0;
		nodeCount = 0;
 
		startIdx = 0;
		endIdx = 0;
	}
 
	private boolean initData(String filePath) throws FileNotFoundException, IOException, NumberFormatException {
		char [][] dataMatrix = loadDataMatrix(filePath);
 
		if( null == dataMatrix )
			return false;
 
		// 인접 행렬 만들기
		makeAdjacentMatrix(dataMatrix);
 
		return true;
	}
 
	private void makeAdjacentMatrix(char [][] dataMatrix) {
		int height = dataMatrix.length;
		int width = dataMatrix[0].length;
 
		nodeCount = height * width;
 
		adjacentMatrix = new int[nodeCount][nodeCount];
 
		for( int i = 0 ; i < height ; i++ ) {
			for( int j = 0 ; j < width ; j++ ) {
				int idx = (i * width) + j;				// current node's number(index)
 
				// Mark All Node is Untouchable Distance
				for( int k = 0 ; k < height * width ; k++ )
					adjacentMatrix[idx][k] = UNTOUCHABLE_DISTANCE;
 
				// 4-way check, including myself
				adjacentMatrix[idx][idx] = 0;
 
				int checkIdx = 0;			
 
				// left
				if( j > 0 ) {
					checkIdx = (i * width) + j - 1;
 
					if( dataMatrix[i][j-1] == '#' )
						adjacentMatrix[idx][checkIdx] = 1;
					else
						adjacentMatrix[idx][checkIdx] = 0;
				}
 
				// right
				if( j + 1 < width ) {
					checkIdx = (i * width) + j + 1;
 
					if( dataMatrix[i][j+1] == '#' )
						adjacentMatrix[idx][checkIdx] = 1;
					else
						adjacentMatrix[idx][checkIdx] = 0;
				}
 
				// up
				if( i > 0 ) {
					checkIdx = ( (i - 1) * width) + j;
 
					if( dataMatrix[i - 1][j] == '#' )
						adjacentMatrix[idx][checkIdx] = 1;
					else
						adjacentMatrix[idx][checkIdx] = 0;
				}
 
				// down
				if( i + 1 < height ) {
					checkIdx = ( (i + 1) * width) + j;
 
					if( dataMatrix[i + 1][j] == '#' )
						adjacentMatrix[idx][checkIdx] = 1;
					else
						adjacentMatrix[idx][checkIdx] = 0;
				}
			}
		}
 
		// test
		//printMatrix(adjacentMatrix);
	}
 
	private char[][] loadDataMatrix(String filePath) throws FileNotFoundException, IOException, NumberFormatException {
		BufferedReader br = new BufferedReader( new InputStreamReader( new FileInputStream(filePath)) 	);
 
		String dataSizeLine = br.readLine();
 
		if( null == dataSizeLine ) {
			System.err.println("파일 내용이 없습니다.");
			return null;
		}
 
		StringTokenizer st = new StringTokenizer(dataSizeLine, " ");
 
		if( 2 != st.countTokens() ) {
			System.err.println("파일 첫 라인의 형식이 맞지 않습니다.(파일의 첫 라인은 '행 열' 만 적혀 있어야 함)");
			return null;
		}
 
		height = Integer.parseInt( st.nextToken() );
		width = Integer.parseInt( st.nextToken() );
 
		if( 0 == height || 0 == width ) {
			System.err.println("행과 열은 1 이상이어야 합니다.");
			return null;
		}			
 
		st = null;
 
		char [][] dataMatrix = new char[height][width];
 
		for( int i = 0 ; i < height ; i++ )
		{
			String line = br.readLine();
 
			if( null == line ) {
				System.err.println("라인 수가 부족합니다.");
				return null;
			}
 
			for( int j = 0 ; j < width ; j++ )
			{
				char ch = line.charAt(j);
 
				if( ch != '.' && ch != '#' && ch != 's' && ch != 'e' ) {
					System.err.println("데이터가 올바르게 입력되지 않았습니다.");
					return null;
				}
 
				if( 's' == ch ) {
					startIdx = (i * width) + j;			// write start node's index
					ch = '.';
				} else if( 'e' == ch ) {
					endIdx = (i * width) + j;			// write end node's index
					ch = '.';
				}
 
				dataMatrix[i][j] = ch;
			}
		}
 
		br.close();
		br = null;
		// dataMatrix Load Complete
 
		// test
		//printMatrix(dataMatrix);
 
		return dataMatrix;
	}
 
	private void printMatrix(int [][] matrix) {
		int height = matrix.length;
 
		if( height <= 0 )
			return;
 
		int width = matrix[0].length;
 
		if( width <= 0 )
			return;
 
		for( int i = 0 ; i < height ; i++ ) {
			for( int j = 0 ; j < width ; j++ ) {
				System.out.print(matrix[i][j] + " ");
			}
 
			System.out.println();
		}
	}
 
	private void printMatrix(char [][] matrix) {
		int height = matrix.length;
 
		if( height <= 0 )
			return;
 
		int width = matrix[0].length;
 
		if( width <= 0 )
			return;
 
		for( int i = 0 ; i < height ; i++ ) {
			for( int j = 0 ; j < width ; j++ ) {
				System.out.print(matrix[i][j] + " ");
			}
 
			System.out.println();
		}
	}
 
	public int calculateShortestPath(String filePath) throws FileNotFoundException,
		IOException, NumberFormatException {
		initValues();
 
		if( !initData(filePath) )
			return UNTOUCHABLE_DISTANCE;
 
		// Dijkstra
		proceedList = new ArrayList();
		readyList = new ArrayList();
 
		// A - Start
		proceedList.add(startIdx);
		for( int i = 0 ; i < nodeCount ; i++ ) {
 
			if( i != startIdx )
				readyList.add(i);
		}
 
		int weightList[] = adjacentMatrix[startIdx].clone();
		int proceedTotalWeight = 0;
		int proceedLastIdx = startIdx;
 
		while( readyList.size() > 0 ) {
			int minIdx = 0;
			int minVal = UNTOUCHABLE_DISTANCE;
			proceedLastIdx = proceedList.get( proceedList.size() - 1 );
 
			Iterator iterReady = readyList.iterator();
 
			while( iterReady.hasNext() ) {
				int readyIdx = iterReady.next().intValue();
 
				int newWeight = proceedTotalWeight + adjacentMatrix[proceedLastIdx][readyIdx];
				if( adjacentMatrix[startIdx][readyIdx] > newWeight ) {
					adjacentMatrix[startIdx][readyIdx] = newWeight;
				}
 
				if( minVal > adjacentMatrix[startIdx][readyIdx] ) {
					minIdx = readyIdx;
					minVal = adjacentMatrix[startIdx][readyIdx];
				}
			}
 
			// minIdx를 readyList에서 뺌
			readyList.remove(new Integer(minIdx));
			proceedList.add(minIdx);
			proceedTotalWeight = minVal;
			proceedLastIdx = minIdx;
		}
 
		return adjacentMatrix[startIdx][endIdx];
	}
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
 
		PracticeDijkstra dijkstra = new PracticeDijkstra();
 
		int shortestWeight = PracticeDijkstra.UNTOUCHABLE_DISTANCE;
 
		try {
			shortestWeight = dijkstra.calculateShortestPath(INPUT_FILE_NAME);
 
			if( UNTOUCHABLE_DISTANCE == shortestWeight ) {
				System.out.println("Not connected");
			} else 	{
				System.out.println("Shortest path's weight : " + shortestWeight);
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
 
	}
 
}