-
Q. 1868 파핑파핑 지뢰찾기(D4)코딩테스트/SWEA_Java 2023. 3. 15. 15:34
DFS와 BFS를 같이 이용해서 풀었다.
모든 방향을 다 생각해야 하므로
dy, dx는 현재 좌표를 제외한 모든 좌표를 순회할 수 있게 만들었다.
1. 처음 입력값을 받을 때 Queue에 폭탄들의 위치를 저장하고, 방문 처리를 했다.
2. 이후 저장된 폭탄들의 위치를 가지고, 폭탄이 없는 근처 칸들에 표시를 했다.
(Board[nextY][nextX]++, BFS 사용)
3. 폭탄이 근처에 있는 모든 칸에 표시가 완료됬다면, 이제 0을 체크할 차례이다.
0으로 표시 될 칸들과 이와 인접한 칸들이 한 번의 클릭에 연쇄적으로 숫자가 표기되므로
1) 먼저 0인 칸을 방문했을 때 그 칸을 방문처리 하고(visited[y][x] = true) click_cnt++를 해준다.
2) 이를 BFS를 이용해 만약 0인 칸 근처에 다른 0인 칸이 있을 경우 그 칸 근처에 대해 다시 BFS순회를 하고,
3) 0이 아닌 칸의 경우 1)에서 클릭했던 한 번으로 연쇄적으로 칸이 보여지므로 방문 처리를 하면 된다.
4. 방문 처리가 안된 칸들이 있을 수 있으므로, 방문 처리가 안된 칸에 대해
순회를 하며 이 칸들은 연쇄적으로 숫자가 표기되는 칸이 아니므로
visited[y][x] = false일 경우 click_cnt++를 해준다.
5. 마지막으로 이후에 결과값인 click_cnt를 출력한다.
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Solution { private static BufferedReader br; static int[][] Board; static boolean[][] Visited; static int[] dy = {1, 0, -1, 1, 0, -1, 1, -1}; static int[] dx = {1, 1, 1, -1, -1, -1, 0, 0}; static int N; static Queue<int[]> BombQueue; static int Click_Cnt; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T; T=sc.nextInt(); BombQueue = new LinkedList<>(); for(int test_case = 1; test_case <= T; test_case++) { N = sc.nextInt(); Board = new int[N][N]; Visited = new boolean[N][N]; Click_Cnt = 0; for (int i=0; i<N; i++) { char[] input = sc.next().toCharArray(); for (int j=0; j<N; j++) { if (input[j] == '*') { BombQueue.add(new int[]{i, j}); Visited[i][j] = true; Board[i][j] = -1; }else { Board[i][j] = 0; } } } while (!BombQueue.isEmpty()) { int[] cur = BombQueue.poll(); int curY = cur[0]; int curX = cur[1]; for (int i=0; i<8; i++) { int nextY = curY + dy[i]; int nextX = curX + dx[i]; if (nextY > (N-1) || nextY < 0 || nextX > (N-1) || nextX < 0) continue; if (Board[nextY][nextX] == -1) continue; Board[nextY][nextX]++; } } for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (!Visited[i][j]) { if (Board[i][j] == 0) { if (!Visited[i][j]) { Click_Cnt++; dfs(i, j); } } } } } for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (!Visited[i][j]) Click_Cnt++; } } System.out.printf("#%d %d\n", test_case, Click_Cnt); } } static void dfs(int y, int x) { Visited[y][x] = true; for (int i=0; i<8; i++) { int nextY = y + dy[i]; int nextX = x + dx[i]; if (nextY > (N - 1) || nextY < 0 || nextX > (N - 1) || nextX < 0) continue; if (Board[nextY][nextX] == 0 && !Visited[nextY][nextX]) { dfs(nextY, nextX); }else if (!Visited[nextY][nextX]) Visited[nextY][nextX] = true; } } }
반응형'코딩테스트 > SWEA_Java' 카테고리의 다른 글
Q. 1206. View (D3) (0) 2023.05.07 Q. 1991 자바 : 트리 순회 (0) 2023.04.13 다익스트라(Dijkstra) 구현_Java (2) 2023.02.25 Q. 1767 자바 : 프로세서 연결하기 (2) 2023.01.31 Q. 3316 자바 : 동아리실 관리하기(D4) (0) 2023.01.22