[SWEA] 파핑파핑 지뢰찾기

Posted on | In |

문제 보러가기

제한사항

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에 하나의 정수 N(1 ≤ N ≤ 300) 이 주어진다. 이는 지뢰 찾기를 하는 표의 크기가 N*N임을 나타낸다.

다음 N개의 줄의 i번째 줄에는 길이가 N인 문자열이 주어진다.

이 중 j번째 문자는 표에서 i번째 행 j번째 열에 있는 칸이 지뢰가 있는 칸인지 아닌지를 나타낸다.

‘’이면 지뢰가 있다는 뜻이고, ‘.’이면 지뢰가 없다는 뜻이다. ‘’와 ‘.’외의 다른 문자는 입력으로 주어지지 않는다.

첫번째 생각

일반적인 BFS 문제이다. 문제의 조건만 잘 고려해서 countmap만 계산해주면 될 것이라고 생각했다.

JAVA Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
	static int N;
	static char[][] map;
	static int[][] countmap;
	static boolean[][] visit;
	static int[] dx = { 1, -1, 0, 0, 1, 1, -1, -1 };
	static int[] dy = { 0, 0, 1, -1, 1, -1, 1, -1 };
	static int res = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			map = new char[N][N];
			countmap = new int[N][N];
			visit = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				String s = sc.next();
				for (int j = 0; j < N; j++) {
					map[i][j] = s.charAt(j);
				}
			}
			count();
			Queue<Point> q = new LinkedList<>();
			res = 0;
			for (int y = 0; y < N; y++) {
				for (int x = 0; x < N; x++) {
					if (countmap[y][x] == 0 && !visit[y][x] && map[y][x] !='*') {
						q.add(new Point(x, y));
						res++;
						while (!q.isEmpty()) {
							Point p = q.poll();
							visit[p.Y][p.X]=true;
							for (int dir = 0; dir < 8; dir++) {
								int tempX = p.X + dx[dir];
								int tempY = p.Y + dy[dir];
								if (InRange(tempX, tempY) && !visit[tempY][tempX] && map[tempY][tempX] != '*') {
									visit[tempY][tempX] = true;
									if (countmap[tempY][tempX] == 0)
										q.add(new Point(tempX, tempY));
								}
							}
						}
						
					}
				}
			}
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (map[y][x] != '*' && !visit[y][x]) {
					res++;
				}
			}
		}
		System.out.println("#"+tc+" "+res);
		}
	}

	public static void count() {
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				for (int dir = 0; dir < 8; dir++) {
					int tempX = x + dx[dir];
					int tempY = y + dy[dir];
					if (InRange(tempX, tempY) && map[tempY][tempX] == '*') {
						countmap[y][x]++;
					}
				}
			}
		}
	}

	public static boolean InRange(int x, int y) {
		if (x >= 0 && y >= 0 && x < N && y < N) {
			return true;
		}
		return false;
	}

	public static class Point {
		int X;
		int Y;

		public Point(int x, int y) {
			X = x;
			Y = y;
		}
	}
}