[백준] 14716번 : 현수막

 

현수막 성공

 

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

2 초

512 MB

6623

4021

3377

63.323%

문제

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

package 문제14716현수막;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
	static int[][] arr;
	static boolean[][] visited;
	static int[] dirx = {-1, 1, 0, 0, -1, -1, 1, 1}; // 상하좌우 + 대각선
	static int[] diry = {0, 0, -1, 1, -1, 1, -1, 1};
	public static void main(String[] args) throws IOException {
		// 상하좌우 대각선으로 인접하여 있다면 한 개의 글자
		System.setIn(new FileInputStream("res/문제14716현수막.txt"));
		// 마당에서 탈출할 수 있는 칸은 어떤 영역에도 속하지 않는다.
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		arr = new int[M][N];
		visited = new boolean[M][N];
		for (int i = 0; i<M; i++) {
			s = br.readLine();
			st = new StringTokenizer(s);
			for (int j = 0; j<N; j++) {
				int k = Integer.parseInt(st.nextToken());
				arr[i][j] = k;
			}
		}// 입력 받기
		int count = 0;
		for (int i = 0; i<M; i++) {
			for (int j = 0; j<N; j++) {
				if (arr[i][j]==1 && visited[i][j]!=true) {
					dfs(i, j);
					count++;
				}
			}
			
		}
		System.out.println(count);
	}
	public static void dfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {x, y});
		visited[x][y] = true;
		while(!queue.isEmpty()) {
			int[] xy = queue.poll();
			int curx = xy[0];
			int cury = xy[1];
			for (int i = 0; i<8; i++) {
				if (curx+dirx[i]>=0 && curx+dirx[i]<arr.length && cury+diry[i]>=0 && cury+diry[i] < arr[0].length) {
					if (arr[curx+dirx[i]][cury+diry[i]]==1 && visited[curx+dirx[i]][cury+diry[i]]!=true) {
						queue.add(new int[] {curx+dirx[i], cury+diry[i]});
						visited[curx+dirx[i]][cury+diry[i]]=true;
					}
				}
			}
		}
	}

}