[DFS&BFS] 백준 - 안전영역

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

2468번: 안전 영역

 

-문제해설

처음 문제를 읽었을 때 강수량이 안나와있어서 당황했는데 걍 0부터 입력값 max까지 반복하면 되는 거였다

첫 번째는 bfs로 문제를 풀었다. 반복문이 많아서 시간초과 나오지 않을까 걱정했는데 빨리 채점됐다.ㅎ

 

대략적인 로직은 다음과 같다.

 

1. 배열 입력을 받을 때 미리 가장 큰 값을 max에 저장시킨다. (강수량을 0부터 max까지 반복하기 위해서)

   배열 입력값은 arr에 저장된다.

 

 

2. 강수량 0부터 max까지 확인하기 위해 반복문 돌린다.

 

 

3. 강수량 반복문에서는 1회 반복될 때마다 visit배열이 초기화되고

강수량보다 작거나 같은 arr입력값이 있으면 해당 행렬에 해당되는 visit배열을 1로 저장해서 방문처리한다.

 

 

4. bfs메소드를 호출한다. bfs의 리턴값은 해당 강수량의 안전영역의 수이다.

대충 예를 들어서

강수량이 1이면 bfs리턴값은 3,

강수량이 2이면 bfs리턴값은 5,

강수량이 3이면 bfs리턴값은 7 이런식으로 나온다.

bfs 리턴값이 가장 큰 놈을 골라야 하므로 Math.max() 메소드로 강수량 반복문 1회반복마다 비교해준다.

 

 

5. bfs메소드 내부 로직은 다음과 같다.

 5.1 큐선언. 큐의 타입은 Point 객체이다(행, 열 값 2개를 저장해야 하므로, 사용자객체를 만들어도된다.)

 

 5.2 visit배열을 모두 순회하기 위해 이중 for문에서 i, j를 1부터 n까지 반복시킨다.

 

 5.3 if문으로 visit[ i ][ j ] == 0 (방문처리 안되어있으면) 경우에 큐에 해당 i, j값을 add시킨다.

 

 5.4 while문으로 큐가 비어질 때까지 반복한다.

 

 5.5 while문 내부에서는 x, y에 현재 큐 맨 위에 있는 행, 열값을 저장하고 맨 위에있는 원소를 poll시킨다.

 

 5.6 상하좌우에서 visit 값이 0 인 곳을 찾기 위해 for문으로 미리 선언한 dx, dy배열 값을 x, y에 더한다.

    이렇게 더한값으로 새로운 nx, ny가 만들어진다.

    dx = [ 0, 0, -1, 1 ] , dy = [ -1, 1, 0, 0 ] 이다.

 

 5.7 visit[ nx ][ ny ]가 0이면 해당 nx, ny를 큐에 넣어주고 visit[ nx ][ ny ]를 1로 방문처리한다.

 

 5.8 이렇게 while문을 계속 돌다가 큐가 비어지면 해당 강수량에 대한 안전영역을 모두 구한 것이므로

     while문을 빠져나와서 안전영역 수를 반환한다.

 

 

6. 5에서 구한 안전영역의 수를 4의 로직에 따라서 어떤 강수량일 때 안전영역이 최대인지 구한다.

 

 

7. 최대 안전영역 수를 출력한다.

 

 

8. 끝~

 

 

 

-자바( bfs )

package bfs_dfs;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ2468 {
	private static int[][] arr;
	private static int[][] visit;
	private static int n;
	private static int[] dx = {0, 0, -1, 1};
	private static int[] dy = {-1, 1, 0, 0};
	
	private static int bfs() {
		int res = 0;
		Queue<Point> que = new LinkedList<Point>();
		
		for( int i=1; i<=n; i++ ) {
			for( int j=1; j<=n; j++ ) {
				if( visit[i][j] == 0 ) {
					visit[i][j] = 1;
					que.add( new Point(i, j) );
					
					while( !que.isEmpty() ) {
						int x = que.peek().x;
						int y = que.peek().y;
						que.poll();
						
						for( int k=0; k<4; k++ ) {
							int nx = x + dx[k];
							int ny = y + dy[k];
							if( nx <= 0 || nx > n || ny <= 0 || ny > n ) continue;
							if( visit[nx][ny]==0 ) {
								que.add( new Point(nx, ny) );
								visit[nx][ny] = 1;
							}
						}
					}
					res++;
				}
			}
		}
		
		return res;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt( br.readLine() );
		arr = new int[n+1][n+1];
		int result = 0;
		
		StringTokenizer st;
		int max = 0;
		for( int i=1; i<=n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( int j=1; j<=n; j++ ) {
				arr[i][j] = Integer.parseInt( st.nextToken() );
				max = Math.max( max, arr[i][j] );
			}
		}
		
		for( int i=0; i<=max; i++ ) {
			visit = new int[n+1][n+1];
			for( int j=1; j<=n; j++ ) {
				for( int k=1; k<=n; k++ ) {
					if( arr[j][k] <= i ) visit[j][k] = 1;
				}
			}
			result = Math.max( bfs(), result );
		}
		System.out.println( result  );
	}
}

 

 

-파이썬( dfs )

def dfs( x, y ):
    visit[x][y] = 1
    
    for i in range( 4 ):
        nx = x + dx[i]; ny = y + dy[i]
        if nx < 1 or nx > n or ny < 1 or ny > n: continue
        if visit[nx][ny] == 0:
            dfs( nx, ny )
    
    return

import sys
sys.setrecursionlimit( 10**6 )
l = sys.stdin.readline
n = int( l() )
arr = []
arr.append( [ 0 for _ in range( n+1 ) ] )

for i in range( 1, n+1 ):
    arr.append( [0] + list( map(int, l().split()) ) )

Max = max( max( arr ) )
ans = []
dx = [0, 0, -1, 1]; dy = [-1, 1, 0, 0]


for i in range( Max+1 ):
    visit = [ [0]*(n+1) for _ in range( n+1 ) ]
    result = 0

    for j in range( 1, n+1 ):
        for k in range( 1, n+1 ):
            if arr[j][k] <= i: visit[j][k] = 1

    for j in range( 1, n+1 ):
        for k in range( 1, n+1 ):
            if visit[j][k] == 0:
                dfs( j, k )
                result += 1

    ans.append( result )

print( max(ans) )