[백준, Java] 1926번, 저울 알고리즘 분류(그래프 탐색, BFS)

문제 링크

1926번: 그림

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 큰 도화지에서 그림은 1로 가로, 세로로 연결된 것으로 정의합니다.

2. 그림의 넓이는 그림에 포함된 1의 개수입니다.

3. 큰 도화지에 그림의 개수와 그림의 최대 넓이를 결과로 출력합니다.

4. 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 도화지 각 위치를 기준으로 그림일 때 BFS탐색을 진행하여 그림의 개수와 넓이를 구합니다.

 

3. 그림의 개수와 그림의 최대 넓이를 결과로 출력합니다.

 

 

BFS 탐색하기.

 

도화지에 다른 그림에 연결되지 않은 1일 때 BFS탐색 진행!!

 

 

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

n : 6
m : 5

1	1	0	1	1
0	1	1	0	0
0	0	0	0	0
1	0	1	1	1
0	0	1	1	1
0	0	1	1	1

 

2. 도화지 각 위치를 기준으로 그림일 때 BFS탐색을 진행하여 그림의 개수와 넓이를 구합니다.

 

(0, 0) BFS 탐색!

 

1	1	0	1	1
0	1	1	0	0
0	0	0	0	0
1	0	1	1	1
0	0	1	1	1
0	0	1	1	1

 

(0, 3) BFS 탐색!

 

1	1	0	1	1
0	1	1	0	0
0	0	0	0	0
1	0	1	1	1
0	0	1	1	1
0	0	1	1	1

 

(3, 0) BFS 탐색!

1	1	0	1	1
0	1	1	0	0
0	0	0	0	0
1	0	1	1	1
0	0	1	1	1
0	0	1	1	1

 

(3, 2) BFS 탐색!

1	1	0	1	1
0	1	1	0	0
0	0	0	0	0
1	0	1	1	1
0	0	1	1	1
0	0	1	1	1

 

3. 그림의 개수와 그림의 최대 넓이를 결과로 출력합니다.

 

1	1	0	1	1
0	1	1	0	0
0	0	0	0	0
1	0	1	1	1
0	0	1	1	1
0	0	1	1	1

그림의 개수 : 4개

그림의 최대 넓이 : 9

4 9을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 도화지에 정보를 저장합니다.
• bfs 함수를 이용하여 방문하지 않은 칠해진 곳을 기준으로 BFS탐색을 진행합니다.
• 모든 탐색이 종료되었을 때 그림의 개수와 최대 넓이를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• bfs함수는 BFS으로 상하좌우 연결된 하나의 그림을 탐색합니다.
• inSpace함수는 (r, c)가 도화지에 존재하는지 확인하는 함수

 

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    //좌표 관련 클래스
    static class Pos{
        int r, c;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    static int[][] map;	//큰 도화지 관련 배열
    static boolean[][] visited;	//큰 도화지 방문확인 배열
    static int[] dr = {-1, 1, 0, 0};	//상하좌우 y 변경값
    static int[] dc = {0, 0, -1, 1};	//상하좌우 x 변경값
    static int n, m, max_width = 0;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = 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++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }
        int team = 0;
        //방문하지 않은 칠해진 곳(1)을 기준으로 BFS 탐색
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(map[i][j] == 1 && !visited[i][j]){
                    visited[i][j] = true;	//방문 확인
                    bfs(i, j);	//BFS탐색 진행
                    team++;	//그림 개수 증가
                }
            }
        }
        //그림 개수와 그림 최대 넓이 BufferedWriter 저장
        StringBuilder sb = new StringBuilder();
        sb.append(team).append("\n").append(max_width);
        bw.write(sb.toString());
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색을 진행하여 그림을 연결하는 함수
    static void bfs(int r, int c){
        Queue<Pos> queue = new ArrayDeque<>();
        queue.add(new Pos(r, c));	//시작 위치 Queue 저장
        int width = 1;
        //BFS탐색 진행
        while(!queue.isEmpty()){
            Pos cur = queue.poll();
            //상하좌우 탐색 진행
            for(int i=0;i<4;i++){
                int tempR = cur.r + dr[i];
                int tempC = cur.c + dc[i];
                //방문하지 않은 칠해진 곳(1)일 때
                if(inSpace(tempR,tempC) && !visited[tempR][tempC] && map[tempR][tempC] == 1){
                    visited[tempR][tempC] = true;	//방문 확인
                    queue.add(new Pos(tempR,tempC));	//Queue 저장
                    width++;	//넓이 증가
                }
            }
        }
        //최대 넓이인지 비교
        max_width = Math.max(max_width, width);
    }
    //(y, x)가 도화지에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c){
        //도화지가 존재할 때
        if(r >= 0 && c>= 0 && r < n && c < m)
            return true;
        return false;		//도화지에 존재하지 않을 때
    }
}