*이 문제는 Programming Challenges : 알고리즘 트레이닝 북에 출제된 문제입니다.
지뢰 찾기(Minesweeper)
이 문제는 문제 자체가 어렵진 않지만 코드를 깔끔하게 작성하는 연습을 하기에는 좋은 문제이다. 코드를 깔끔하게 작성하기 좋은 팁은 다음과 같다.
1. 지뢰 찾기 맵을 char[][] map; 로 만들고, 지뢰가 아닌 곳은 아스키 문자 '0'을 넣는다.
이렇게 하면 주위에 지뢰가 있을 때 map[i][j] ++를 호출해주면 자동으로 아스키 문자가 '1', '2', '3'.... 순서로 1씩 증가 된다.
2. 지뢰를 만나서 주변 8개 지뢰에 대한 카운트를 증가 시킬 때 해야 할 일을 함수로 빼낸다.
"지뢰 주변"을 탐색하면서 맵을 벗어난 곳을 체크하기가 수월해진다.
3. 카운트 증가 조건에 맞으면 업데이트 하지 말고 조건에 맞지 않을 경우 리턴한다.
리턴문(return)을 잘 활용하면 로직이 복잡해지는 것을 막을 수 있다.
아래는 직접 구현한 지뢰 찾기 소스이다.
class MineSweeper{
Input input = new Input();
private char[][]map;
int n = 0;// row
int m = 0;// column
int iteration = 0;
public void run(){
while(true){
readRowColumn(); // row(n)와 column(m) 값을 입력 받는다.
if(isExit()) return; // n == m == 0 이면 리턴한다.
initMap(); // 맵을 생성한다.
loadMap(); // 맵을 입력 받는다.
calculateMap(); // 맵을 계산한다.
printResult(); // 맵을 출력한다.
}
}
private boolean isExit(){
if(n == 0 && m == 0) return true;
return false;
}
private void readRowColumn(){
String line = input.readLine();
StringTokenizer token = new StringTokenizer(line);
n = Integer.parseInt(token.nextToken());// row
m = Integer.parseInt(token.nextToken());// column
}
private void initMap(){
map = new char[n][m];
}
private void loadMap(){
for(int i = 0; i < n; i++){
String line = input.readLine();
for(int j = 0; j < m; j++){
map[i][j] = line.charAt(j);
if(map[i][j] == '.') map[i][j] = '0';
}
}
}
private void calculateMap(){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(map[i][j] == '*') addCountAround(i, j);
}
}
}
private void addCountAround(int x, int y){
for(int i = x - 1; i <= x + 1; i++){
for(int j = y - 1; j <= y + 1; j++){
addCount(i, j);
}
}
}
private void addCount(int x, int y){
if(x < 0 || x >= n) return;
if(y < 0 || y >= m) return;
if(map[x][y] == '*') return;
map[x][y]++;
}
private void printResult(){
iteration++;
if(iteration != 1) System.out.println();
System.out.println("Field #" + iteration + ":");
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
System.out.print(map[i][j]);
}
System.out.println();
}
}
}
이 구현에서 핵심 부분은 calculateMap() 메소드와 이 메소드에 호출되는 addCountAround() 그리고 addCount() 메소드일 것이다.
calculateMap()은 가로와 세로 방향으로 for문을 돌아서 모든 맵을 방문하는 일을 담당한다. 만약 이 과정에서 지뢰(*)를 만나면 addCountAround(i, j) 메소드를 호출하는 것으로 자기 임무를 마친다.
addCountAround()는 지뢰 주변의 9개 타일(자기 자신 포함) 타일들을 방문한다. 그리고 addCount() 메소드를 호출하는 것으로 자기 임무를 마친다.
addCount() 메소드가 실질적으로 카운트를 증가시킨다. 이 때 중요한 것은 예외 처리이다. 만약 타일이 지뢰이거나 맵의 경계를 넘어갔다면 카운트를 증가시키면 안된다. 따라서 미리 예외의 경우들을 체크하고 적절한 타일이 아니라면 리턴한다. 그리고 정상적인 타일인 경우에면 카운트를 증가시킨다.
또한 run() 메소드에서는 문제에서 주어진 절차를 모두 메소드로 만들고 절차에 맞는 적절한 이름을 할당해 줌으로써 전체 동작이 어떤지를 한눈에 알 수 있도록 만들어 주는 것이 코드를 깔끔하게 만들 수 있는 비결이다.
중간에 Input 클래스를 사용하는데 이에 대해서는 [Programming Challenges]Sample 및 표준 입력 데이터 이중화 글을 참고하기 바란다.
'7.알고리즘' 카테고리의 다른 글
| [Programming Challenges]Sample 및 표준 입력 데이터 이중화 (0) | 2016.10.06 |
|---|
programmingChallenges.zip
