[Solved]/코딩테스트

섬나라 아일랜드 (BFS, DFS)

응파카 2023. 3. 30. 10:27

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