swea 1868 <파핑파핑 지뢰찾기 >

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE

SW Expert Academy

이 문제는 DFS 또는 BFS 문제의 심화 문제이다. 이문제에서 알아야 할 것은 어디를 먼저 클릭해야 더욱 많이 퍼지는 가이다. 이것을 알아보기 위해서 이 그림을 보자

 

이 모양을 보면 알 수 있듯이 지뢰가 8방향으로 없는 곳을 먼저 터트리게 되면 계속해져 퍼질 수 있다.

 

문제 풀이

1. 클릭할 수 있는 위치를 모두 Queue <Point>에 넣는다. Queue사이즈를 저장한다.(전체 수)
2. 8방향으로 퍼질수 있으면 퍼트린다. 아니라면 종료 --> bfs로 실시
3. 8방향으로 퍼질 수 있다면 클릭할 필요없는 수를 전체 수에서 빼준다.

흐름은 이런식으로 진행된다. 반대로 클릭할 필요 없는 수를 빼는 것이 아닌 클릭한 수를 계산해줬다면 훨씬 간단해졌을 문제이다.

 

이렇게 다양한 방법으로 문제를 접근하고 풀어보는것이 알고리즘의 실력을 늘리는 지름길이다.

 

전체 코드

package hw1105;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class 지뢰찾기 {

	static int t, n, result,
			dir[][] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };// 8방향
	static String map[];
	static boolean visit[][];
	static ArrayList<Point> a;
	static Queue<Point> q;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= t; tc++) {
			n = Integer.parseInt(br.readLine());
			a = new ArrayList<Point>();
			map = new String[n];
			visit = new boolean[n][n];
			for (int i = 0; i < n; i++) {
				map[i] = br.readLine();
				for (int j = 0; j < n; j++) {
					if (map[i].charAt(j) == '.') {
						a.add(new Point(i, j));
					}
				}
			} // 맵에 저장
			result = a.size();// 일단 모든 클릭 횟수
			for (int i = 0; i < a.size(); i++) {
				Point next = a.get(i);
				if (visit[next.x][next.y]) {
					continue;
				}
				q=new LinkedList<Point>();
				q.add(new Point(next.x,next.y));
				result-=bfs();
			}
			System.out.println("#"+tc+" "+result);
		}
	}
	private static int bfs() {
		// TODO Auto-generated method stub
		int sum=0;
		while(!q.isEmpty()) {
			Point next=q.remove();
			boolean flag = true;
			for (int j = 0; j < 8; j++) {
				int x1 = next.x + dir[j][0];
				int y1 = next.y + dir[j][1];
				if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= n||visit[x1][y1])
					continue;
				if (map[x1].charAt(y1) == '*')
					flag = false;
			}
			if (flag) {
				visit[next.x][next.y]=true; 
				for (int j = 0; j < 8; j++) {
					int x1 = next.x + dir[j][0];
					int y1 = next.y + dir[j][1];
					if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= n||visit[x1][y1])
						continue;
					visit[x1][y1]=true;
					q.add(new Point(x1,y1));
					sum++;
				}
			}
		}
		return sum;
	}

}