[Java] 백준 14716번 : 현수막

1. 문제

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

14716번: 현수막

 

 

2. 풀이 과정

8방향 탐색은 dfs로 구현하였으며, 방문 체크는 입력 값을 2로 바꾸어 표시했다.

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

public class Main {
    static int N, M, map[][];
    static int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

    public static void dfs(int x, int y){
        map[x][y] = 2;
        for(int i=0; i<8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny] != 1){
                continue;
            }
            dfs(nx, ny);
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st. nextToken());
        map = new int[N][M];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int res = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(map[i][j] == 1){
                    dfs(i, j);
                    res++;
                }
            }
        }
        System.out.println(res);
    }
}

 

 

결과