백준 1926_그림(JAVA)

 

www.acmicpc.net/problem/1926

1926번: 그림

[문제 풀이]

깊이 우선 탐색을 이용하여 문제를 풀었습니다.

 

이 문제는 2차원 배열에 대한 정보가 주어지고 2차원 배열에서 1로 연결된 그림의 갯수가 최대 그림의 크기를 찾는 문제였습니다. 문제를 푼 방법은 배열을 순회하며 1이 시작되는 좌표를 찾고 깊이 우선으로 탐색하며 확인한 좌표들은 마킹을 해주는 식으로 풀었습니다.

 

코드 설명

• 입력으로 주어진 값을 받아 배열에 저장해주고 방문을 확인할 배열을 똑같이 선언해 줍니다.
• 입력 받은 배열을 반복문을 통해 순회 하면서 방문하지 않았으면서 배열의 값이 1이라면 그림의 값을 1로 초기화 해주고 탐색을 시작해줍니다.
• 그림의 값이 현재의 최대 그림의 값보다 크면 최대 그림의 값을 바꿔줍니다.
• 탐색하는 배열의 좌표의 상하좌우의 값이 1이면서 방문하지 않았다면 그림의 크기를 키워주고 탐색합니다.

[코드]

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

class Main{
	
	static int n, m, answer = 0, temp_square = 0;
	static int[][] map;
	static int[][] visit;
	
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	
	public static void DFS(int idx, int jdx) {
		
		if(answer < temp_square)
			answer = temp_square;
		
		for(int i = 0; i < 4; i++) {
			
			int nx = idx + dx[i];
			int ny = jdx + dy[i];
			
			if(nx < 0 || ny < 0 || nx >= n || ny >= m || visit[nx][ny] == 1 || map[nx][ny] == 0)
				continue;
			
			temp_square++;
			visit[nx][ny] = 1;
			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];
		visit = 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 picture_cnt = 0;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				
				if(visit[i][j] == 0 && map[i][j] == 1) {
					visit[i][j] = 1;
					temp_square = 1;
					DFS(i,j);
					picture_cnt++;
				}
			}
		}
		
		System.out.println(picture_cnt);
		System.out.println(answer);
		
	}
}