백준 | 14716번. 현수막 - DFS & BFS 풀이

⬛ 백준 14716번. 현수막 - DFS & BFS 풀이

https://www.acmicpc.net/problem/14716

14716번: 현수막

문제

ANT가 처음 알고리즘 대회를 개최하게 되면서 현수막을 내걸었다.

저번 학기 영상처리 수업을 듣고 배웠던 지식을 최대한 응용 해보고 싶은 혁진이는 이 현수막에서 글자가 몇 개인지 알아보는 프로그램을 만들려 한다.

혁진이는 우선 현수막에서 글자인 부분은 1, 글자가 아닌 부분은 0으로 바꾸는 필터를 적용하여 값을 만드는데 성공했다.

그런데 혁진이는 이 값을 바탕으로 글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각만 하였다.

혁진이가 필터를 적용하여 만든 값이 입력으로 주어졌을 때, 혁진이의 생각대로 프로그램을 구현하면 글자의 개수가 몇 개인지 출력하여라.

입력

첫 번째 줄에는 현수막의 크기인 M와 N가 주어진다. (1 ≤ M, N ≤ 250)

두 번째 줄부터 M+1 번째 줄까지 현수막의 정보가 1과 0으로 주어지며, 1과 0을 제외한 입력은 주어지지 않는다.

출력

혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라.

---

💚 풀이

• 대각선 + 4방향 모두 포함해서 탐색의 범위는 총 8방향이 된다.

//8방향 탐색 
static int[] dx = {0, 0, 1, -1, -1, -1, 1, 1};
static int[] dy = {1, -1, 0, 0, -1, 1, -1, 1};

• DFS 이든, BFS이든 위의 8방향 탐색 변수를 미리 선언해주고,
• map[i][j]의 값이 1인 경우에 한해서, DFS라면 계속해서 다음 정점이 1인 경우까지 쭉 깊이 탐색하여 복귀하는 그 호출 횟수 == 글자 개수 가 되는 것이고,
• BFS라면 인접 정점이 계속해서 1인 경우에 한해서 뻗어가며 탐색하다가 더 이상 없으면 멈추는 그 호출 횟수 = 글자 개수 가 되는 것이다.
• 이에 따라 작성한 코드는 아래와 같다.

---

💚 (1) 나의 풀이 - DFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*14716번 현수막 - DFS & BFS 풀이 */
public class Main {
	//8방향 탐색
	static int[] dx = {0, 0, 1, -1, -1, -1, 1, 1};
	static int[] dy = {1, -1, 0, 0, -1, 1, -1, 1};

	static int M, N;
	static int[][] map;
	static boolean[][] visited;
	//DFS
	static void DFS(int x, int y ) {
		visited[x][y] = true;//방문체크
		
		for(int k=0; k<8; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(nx <0 || ny <0 || nx>=M || ny>=N || map[nx][ny] == 0) continue;
			
			if(!visited[nx][ny] && map[nx][ny]==1) { 
				DFS(nx, ny);//더 깊이 탐색
			}
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		M = kb.nextInt();//행
		N = kb.nextInt();//열
		map = new int[M][N];
		visited =new boolean[M][N];
		
		//데이터 입력받기 
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = kb.nextInt();
			}
		}
		
		int cnt = 0;
		//호출 
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				if(!visited[i][j] && map[i][j] == 1) {
					//방문 전이면서 1인 애한테 탐색
					//그 호출 횟수 == 덩어리 개수 
					DFS(i, j);
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}
}

---

💚 (2) 나의 풀이 - BFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*14716번 현수막 - DFS & BFS 풀이 */
public class Main {
	//8방향 탐색
	static int[] dx = {0, 0, 1, -1, -1, -1, 1, 1};
	static int[] dy = {1, -1, 0, 0, -1, 1, -1, 1};

	static int M, N;
	static int[][] map;
	static boolean[][] visited;

	//BFS
	static void BFS(int x, int y) {
		Queue<int[]> Q = new LinkedList<>();
		Q.offer(new int[] {x, y});//담고
		visited[x][y] = true;
		
		while(!Q.isEmpty()) {
			int len =Q.size();
			for(int i=0; i<len; i++) { //레벨 탐색 
				int[] cur = Q.poll();//하나씩 뽑고 
				for(int k=0; k<8; k++) {
					int nx = cur[0] + dx[k];
					int ny = cur[1] + dy[k];
					if(nx <0 || ny<0 || nx >= M || ny>=N || map[nx][ny] == 0) continue;
					if(!visited[nx][ny] && map[nx][ny]==1) {
						visited[nx][ny] = true;
						Q.offer(new int[] {nx, ny});
					}
				}
			}
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		M = kb.nextInt();//행
		N = kb.nextInt();//열
		map = new int[M][N];
		visited =new boolean[M][N];
		
		//데이터 입력받기 
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = kb.nextInt();
			}
		}
		
		int cnt = 0;
		//호출 
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				if(!visited[i][j] && map[i][j] == 1) {
					//방문 전이면서 1인 애한테 탐색
					//그 호출 횟수 == 덩어리 개수 
					BFS(i, j);
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}
}