프로그래밍 갤러리에서 올라온 문제를 한 번 풀어 보았다.
실무 작업만 하다가 오랜만에 자료구조/알고리즘 문제를 푸니까 좀 어렵기도 하고 전공 기억도 가물가물했다.
사실 아무런 정보도 없었으면 좀 헤맬 뻔 했는데, 리플에 Dijkstra 얘기가 나와서 해결 실마리를 찾을 수 있었다.
브로디에게 납치를 당한 뒤 창고에 갇힌 다오는 서둘러 탈출할 방법을 찾고 있다.
가로막힌 블록을 맨손으로 부수며 길을 만들어야 하는데 최소 몇 개의 블록을 부수어야 출구에 도달할 수 있을까?
이동은 상하좌우 네 방향으로만 가능하며, 블록이 여러 겹으로 놓인 장애물도 존재한다.
하나의 프로그램을 작성하여 첨부 파일 map1.txt, map2.txt, map3.txt의 세 가지 입력에 대하여 각각 답을 구하시오.
입력<
5 6 // 행의 수 n, 열의 수 m
s.#… // 첫 번째 행
..#### // 두 번째 행
#.#..# // 각 행은 m개의 문자로 이루어져 있고, 각 문자의 의미는 아래와 같다
..###. // 빈 공간: . 블록: # 다오: s 출구: e
###..e // n번째 행
출력
2 // 탈출하기 위해 부수어야 하는 최소 블록 개수
일단 창고의 각 공간을 노드로 보면, 창고는 bi-directional weight 가 존재하는 그래프이다.
(bi-directional로 해야 하는 이유는, 두 개의 노드가 연결되는 간선이 빈 공간 -> 블록, 블록 -> 빈 공간의 서로 다른 weight가 생길 수 있기 때문이다.)
그래프에 대해 블록 노드로 가는 간선의 weight는 1, 나머지는 0 으로 매겨서 인접 행렬을 만든 다음, Dijkstra 최소거리 알고리즘을 적용하면 s -> e에 대한 최소 weight가 구해진다.
위에서 블록 노드로 가는 경우에만 1의 weight를 적용하였으므로 최소 weight가 부순 블록의 갯수가 된다.
자바로 구현해 봤다. 사실 좀 걸렸다. 코드 정리하면서 코딩하기도 했고, Dijkstra도 다시 상기시켜서 이해하는 데 시간이 좀 걸렸다.(설명이 쉽게 되어 있는 포스트가 있어 도움이 많이 됐다.) 전공 공부를 좀 열심히 해야 할 듯…
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();
}
}
} |
