문제#
- 링크로 대체
풀이 및 주저리..
간단한 BFS 문제였다. 먼저 맵을 char 형태의 배열로 받아 기록하고 방문했었는지의 여부를 boolean 배열을 활용해 만들어놓고 문제를 시작했다. 단지를 오름차순으로 구하기 위해서 PriortyQueue 를 활용했고 쉽게 풀 수 있었다. 단지별로 묶는 걸 잘 생각해서 해야 하기 때문에 시뮬레이션적인 요소도 포함되어있는 문제였다.
코드
package baekjoon.algorithm.dfsbfs;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class Problem2667 {
static final int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
char[][] map = new char[n][n];
boolean[][] isMappedArr = new boolean[n][n];
PriorityQueue<Integer> answerPriorityQue = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
map[i] = sc.nextLine().toCharArray();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '1' && !isMappedArr[i][j]) {
Queue<Integer> que = new LinkedList<>();
int answer = 1;
que.add(i);
que.add(j);
isMappedArr[i][j] = true;
while (!que.isEmpty()) {
int x = que.poll();
int y = que.poll();
for (int k = 0; k < 4; k++) {
int mX = x + dx[k];
int mY = y + dy[k];
if (mX >= 0 && mX < n && mY >= 0 && mY < n) {
if (map[mX][mY] == '1' && !isMappedArr[mX][mY]) {
isMappedArr[mX][mY] = true;
que.add(mX);
que.add(mY);
answer++;
}
}
}
}
answerPriorityQue.add(answer);
}
}
}
System.out.println(answerPriorityQue.size());
while (!answerPriorityQue.isEmpty()) {
System.out.println(answerPriorityQue.poll());
}
}
}기억에 남길 것!
- 최근 문제의 대세는 시뮬레이션 + 브루트포스