[백준 1926번] 그림 - JAVA

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

1926번: 그림

풀이

사용한 알고리즘 : DFS

 

풀이전략

1. 입력에 대응되는 그래프를 2차원 배열에 저장한다.

2. (0,0)에서 (n-1,m-1) 까지의 점에서 동서남북 모든 방향으로 dfs 탐색을 한다.

3. dfs 탐색 중 한 번이라도 방문하지 않은 지점을 통과하면 paintingCount를 증가시킨다.

4. 하나의 지점에서 최대로 방문한 횟수를 maxCount에 저장한다.

5. paintingCount와 maxCount를 출력한다.

 

제출코드

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

public class Main {

    static int n,m;
    static int graph[][];
    static boolean visited[][];
    static int dx[]={-1,0,1,0};
    static int dy[]={0,1,0,-1};
    static int count=0;
    static int maxCount=0;

    static void dfs(int x,int y){
        if(!visited[x][y] && graph[x][y]==1){
            visited[x][y]=true;
            ++count;
            if(maxCount<count) maxCount=count;

            for(int i=0;i<4;++i){
                int mx=x+dx[i];
                int my=y+dy[i];
                if(mx>=0 && mx<n && my>=0 && my<m){
                    dfs(mx,my);
                }
            }
        }
    }
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph=new int[n][m];
        visited=new boolean[n][m];

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

        int paintingCount=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                count=0;
                dfs(i,j);
                if(count!=0) ++paintingCount;
            }
        }
        System.out.println(paintingCount);
        System.out.println(maxCount);
    }
}