[백준] [14716] 현수막 (BFS) (JAVA)

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

14716번: 현수막

---

현수막 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

3862

2234

1866

61.564%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

8 19
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0
0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

예제 출력 1 복사

3

---

※ JAVA코드 (현수막)

import java.io.*;
import java.util.*;

public class Main {
	static int M, N;
	
	static int[][] map;
	static boolean[][] visited;
	
	// 상하좌우 이동
	static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
	static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
	
	// 좌표를 담을 클래스
	static class Node {
		int x, y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	// 넓이우선 탐색
	public static void bfs(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(x, y));
		visited[x][y] = true;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			
			for(int i = 0; i < 8; i++) {
				int nextX = now.x + dx[i];
				int nextY = now.y + dy[i];
				
				// 맵의 범위를 넘어가면 탐색하지 않는다
				if(nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) {
					continue;
				}
				
				// 이미 방문했거나 글자가 아닌부분은 탐색하지 않는다
				if(visited[nextX][nextY] == true || map[nextX][nextY] == 0) {
					continue;
				}
				
				// 방문체크
				visited[nextX][nextY] = true;
				// 큐에담는다
				q.offer(new Node(nextX, nextY));
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		map = new int[M][N];
		visited = new boolean[M][N];
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int cnt = 0;
		for(int i = 0; i < M; i++) {
			for(int j = 0; j < N; j++) {
				// 미방문이고 글자인 부분이면 탐색시작
				if(visited[i][j] == false && map[i][j] == 1) {
					cnt++;
					bfs(i, j);
				}
			}
		}
		
		System.out.println(cnt);
	}
}

---

※ 생각정리 (현수막)

백준 현수막문제는 BFS탐색을 통해 문제를 해결할 수 있다.

1. 반복문을 통해 (0, 0) 좌표부터 탐색을 시작한다.

2. 방문배열에서 아직 방문하지 않은 배열위치이며, 맵배열에서 글자가 있은 좌표를 찾아서 탐색에 들어간다.

3. 현재위치에서 상, 하, 좌, 우, 대각선 방향에서 글자가 있는지 탐색하여 같은 현수막에 있는 부분은 전부 방문체크를 한다.

4. 한번의 현수막이 채워지고 나서는 카운트를 해서 총 현수막의 개수를 센다.

 

-새벽코딩-