BFS
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Node{
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int answer = 0, n;
static int[] dx = {1, 1, 1, -1, -1, -1, 0, 0};
static int[] dy = {1, 0, -1, 1, 0, -1, 1, -1};
static int[][] board;
static Queue<Node> queue = new LinkedList<>();
public void BFS(int x, int y) {
queue.offer(new Node_13(x, y));
while(!queue.isEmpty()) {
Node node = queue.poll();
for(int i=0; i<8; i++) {
int nx = node.x + dx[i];
int ny = node.y + dy[i];
if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]==1) {
board[nx][ny] = 0;
queue.offer(new Node_13(nx, ny));
}
}
}
}
public void solution() {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(board[i][j] == 1) {
answer++;
board[i][j] = 0;
BFS(i, j);
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Main T = new Main();
Scanner kb = new Scanner(System.in);
n = kb.nextInt();
board = new int[n][n];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++)
board[i][j] = kb.nextInt();
}
T.solution();
System.out.println(answer);
}
}
DFS
import java.util.Scanner;
public class Main {
static int answer = 0, n;
static int[] dx = {1, 1, 1, -1, -1, -1, 0, 0};
static int[] dy = {1, 0, -1, 1, 0, -1, 1, -1};
static int[][] board;
public void DFS(int x, int y) {
for(int i=0; i<8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]==1) {
board[nx][ny] = 0;
DFS(nx, ny);
}
}
}
public void solution() {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(board[i][j] == 1) {
answer++;
board[i][j] = 0;
DFS(i, j);
}
}
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
n = kb.nextInt();
board = new int[n][n];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++)
board[i][j] = kb.nextInt();
}
T.solution();
System.out.println(answer);
}
}
'Solved > 코딩테스트' 카테고리의 다른 글
최대점수 구하기 (냅색 알고리즘) (0) | 2023.04.05 |
---|---|
뮤직비디오(결정알고리즘) (0) | 2023.04.03 |
토마토(BFS 활용) (0) | 2023.03.29 |
후위연산식 문제 (Stack) (0) | 2023.03.18 |
임시반장 정하기 문제 (0) | 2023.03.17 |