백준 14716번 : 현수막

 문제

www.acmicpc.net/problem/14716

14716번: 현수막

14716 현수막

 

 구현 방법

dfs로 8방탐색 해주었습니다.

해당 값이 1이면 dfs를 실행시켰습니다. 8방을 탐색하여 1인 경우 0으로 바꿔 방문체크를 해주고 dfs를 호출하여 탐색한 값을 넣어주었습니다.

 

 구현 코드

package BOJ.Silver.bfsdfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B14716_현수막 {
	static int R, C, cnt;
	static int[][] map;
	static int[][] deltas = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		for (int r=0;r<R;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<C;c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		// 입력완료
		for (int r=0;r<R;r++) {
			for (int c=0;c<C;c++) {
				if (map[r][c] == 1) {
					dfs(r, c);
					cnt++;
				}
			}
		}
		
		System.out.println(cnt);
	}
	
	static void dfs(int r, int c) {
		map[r][c] = 0;
		for (int d=0;d<deltas.length;d++) {
			int nr = r+deltas[d][0];
			int nc = c+deltas[d][1];
			if (isIn(nr, nc) && map[nr][nc]==1) {
				map[nr][nc]=0;
				dfs(nr, nc);
			}
		}
		return;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!