[SWEA] 1868 파핑파핑 지뢰찾기 (D4^ / BFS) - Java

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE&problemTitle=1868&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

문제 해석

- 문제 해석
지뢰 : *
지뢰가 없는 칸 : .

주변 8방에 지뢰가 있으면 숫자를 출력함
주변 8방에 지뢰가 없으면 나머지 8방 숫자를 모두 출력함(x)
지뢰 경계 부분까지 모두 출력함 (일반적인 지뢰찾기와 동일한 로직)

지뢰가 있는 칸을 제외한 다른 모든 칸의 숫자들이 표시되려면 최소 몇 번을 클릭해야 하는가?


- 각 테스트 케이스 별 입력
첫 번째 줄 : N # 표의 한쪽 면 크기
나머지 줄 : N줄의 지뢰 정보

 

 

코드

package algo.swea.d4_1868;

import java.io.*;
import java.util.*;

public class Solution {
	static char[][] map;
	static boolean[][] v;
	static int answer;

	static int[] dx = { -1, -1, -1, 0, 1, 1, 1, 0 };
	static int[] dy = { -1, 0, 1, 1, 1, 0, -1, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int T = Integer.parseInt(st.nextToken());

		for (int test_case = 1; test_case <= T; test_case++) {
			// input
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // 배열 크기

			answer = 0;

			map = new char[N][N];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				String s = st.nextToken();
				for (int j = 0; j < N; j++) {
					map[i][j] = s.charAt(j);
				}
			}

			// 1회 탐색 (배열 -> 숫자로 변경)
			v = new boolean[N][N];
			bfs(0, 0);

			// 2회 탐색
			v = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == '0' && v[i][j] == false) { // 0이고 방문한 적이 없으면
						bfs2(i, j);
					}
				}
			}

			// 3회 탐색
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (v[i][j] == false && map[i][j] != '*') { // 나머지 count
						answer++;
					}
				}
			}
			System.out.println("#" + test_case + " " + answer);

		} // [E] test_case
	}

	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	private static void bfs(int x, int y) {
		Queue<Point> q = new LinkedList<>();
		q.offer(new Point(x, y));
		v[x][y] = true;

		while (!q.isEmpty()) {
			Point p = q.poll();

			int bombCount = 0;

			for (int i = 0; i < dx.length; i++) {
				int cx = p.x + dx[i];
				int cy = p.y + dy[i];

				if (cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length) {
					if (v[cx][cy] == false) {
						q.offer(new Point(cx, cy));
						v[cx][cy] = true;
					}

					if (map[cx][cy] == '*') {
						bombCount++;
					}
				}

				if (i == dx.length - 1 && map[p.x][p.y] == '.') { // 마지막 반복이고 폭탄이 아니면
					map[p.x][p.y] = (char) (bombCount + '0');
				}
			}
		}
	}

	private static void bfs2(int x, int y) {
		Queue<Point> q = new LinkedList<>();
		Queue<Point> tempQ = new LinkedList<>();
		q.offer(new Point(x, y));
		v[x][y] = true;
		answer++;

		while (!q.isEmpty()) {
			Point p = q.poll();

			if (map[x][y] == '0') { // 첫 시작이 0이라면
				for (int i = 0; i < dx.length; i++) {
					int cx = p.x + dx[i];
					int cy = p.y + dy[i];

					if (cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length && map[cx][cy] != '*') {
						if (map[cx][cy] == '0' && v[cx][cy] == false) {
							q.offer(new Point(cx, cy));
						}
						v[cx][cy] = true;
					}
				}
			}
		}
	}

}

 

 

 

코드 해석

해당 문제는 0인 부분을 눌렀을때 노출되는 부분을 찾는 것이 중요하고, 이는 BFS의 덩어리를 찾는 문제와 비슷하다고 볼 수 있습니다.

 

 

저는 총 3번 2중 for문을 통해서 배열을 탐색하는 방법을 선택하였습니다.

 

먼저 첫 번째 탐색에서는 bfs를 통해 주변 지뢰 여부를 확인하고, '.'를 숫자로 바꾸는 작업을 수행하였습니다.

 

두 번째 탐색에서는 마찬가지로 bfs를 통해 주변을 탐색하는데 방문하지 않은 0인 경우만 탐색을 수행하며, bfs를 통해 탐색된 부분을 visited 처리하여 이후 탐색하지 않도록 하였습니다.

즉 두번째 탐색에서는 0의 주변에 있는 한 번 눌렀을 때 나오는 모든 조건을 찾아서 count하였습니다.

두 번째 탐색

 

마지막 세 번째 탐색에서는 두 번째 탐색에서 걸러지지 못한 나머지 숫자들을 누르는 조건이라고 생각하시면 됩니다. 이들은 연결되어 있더라도 서로 영향을 미치지 못하기 때문에 bfs가 아닌 단순 count로 처리하였습니다.

 

 

 

발생한 문제 & 해결 방안

일반적인 지뢰 찾기 문제인데, 문제를 읽고 제대로 이해하지 못하여, 0인 부분을 누르면 주변 8방만 나오는줄 알고 헛고생을 하였다.

 

문제와 예제를 잘 읽어보고 문제를 풀어야겠다.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice