[백준] S1 14716번 현수막 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

14716번: 현수막

[문제] 

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

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

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

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

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

[입력]

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

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

[출력]

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

 

---

[풀이]

1. 입력을 받아 값들을 담아준다.

2. 배열을 탐색하며, 방문한 적이 없고 글자인 경우 dfs 탐색을 한다.

3. dfs 탐색을 하고 넘어오면 총 문자 수를 1 증가시킨다.

4. 결과를 출력한다.

[접근]

1. DFS를 사용하면 되겠다고 생각하였고, 문제에서 상하좌우만이 아닌 대각선을 포함하였기에 사방탐색이 아닌 팔방탐색을 하면 되겠다고 생각하였다.

[코드]

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

public class Main {
	static int m, n;
	static int map[][];
	static boolean visited[][];
	static int cnt;
	
	static int dr[] = {0, 0, -1, -1, -1, 1, 1, 1};
	static int dc[] = {-1, 1, 0, -1, 1, 0, -1, 1};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer 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());
			}
		}
		
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				// 글자이면서 미방문이면
				if (map[i][j] == 1 && !visited[i][j]) {
					// dfs 탐색
					dfs(i, j);
					// 문자 수 증가
					cnt++;
				}
			}
		}
		
		System.out.println(cnt);
	}
	
	public static void dfs(int x, int y) {
		visited[x][y] = true;
		
		// 팔방탐색
		for (int i = 0; i < 8; i++) {
			int nx = x + dr[i];
			int ny = y + dc[i];
			
			// 범위 안, 미방문, 문자일 경우
			if ((nx >= 0 && ny >= 0 && nx < m && ny < n) && !visited[nx][ny] && map[nx][ny] == 1) {
				// 방문처리
				visited[nx][ny] = true;
				// 추가 dfs 탐색
				dfs(nx, ny);
			}
		}
	}
}