[백준/java] 2468번 : 안전 영역 - BFS

2468번 : 안전 영역

 

 

728x90

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

2468번: 안전 영역

 

 

어렵지도, 그렇다고 그렇게 쉬운문제는 아니었다.

 

생각보다 놓치기 쉬운 함정들이 있었다.

 

반응형

 

입력의 마지막 설명 중,

" 높이는 1이상 100 이하의 정수이다. "

라는 설명이 있는데, 문제 페이지 맨 마지막 "노트"란을 보면

 

 

라고 나와있다.

 

이것을 고려하지 않는 경우가 더러 있었다고 한다.

bfs로 순환하여 탐색하되, 순환의 높이의 시작은 0부터 100까지여야 한다는 것이다.

 

 

package bfs;

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 SafeZone {
	static int[][] map;
	static boolean[][] visit;
	static int N;
	static int[] dy = {1, 0, -1, 0};
	static int[] dx = {0, 1, 0 , -1};
	static class Node {
		int y, x;
		public Node(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = stoi(br.readLine());
		map = new int[N][N];
		visit = new boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			for (int j = 0; j < N; j++) {
				map[i][j] = stoi(st.nextToken());
			}
		}
		
		int max = 0;
		for (int i = 0; i <= 100; i++) {
			visit = new boolean[N][N];
			max = Math.max(max, bfs(i));
		}
		
		System.out.println(max);
	}
	
	public static int bfs(int n) {
		int ret = 0;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j] <= n || visit[i][j]) continue;
				
				Queue<Node> q = new LinkedList<Node>();
				visit[i][j] = true;
				q.add(new Node(i, j));
				
				while(!q.isEmpty()) {
					Node cur = q.poll();
					
					for (int dir = 0; dir < 4; dir++) {
						int ny = cur.y + dy[dir];
						int nx = cur.x + dx[dir];
						
						if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
						if(map[ny][nx] <= n || visit[ny][nx]) continue;
						
						visit[ny][nx] = true;
						q.add(new Node(ny, nx));
					}
				}
				
				ret++;
			}
		}
		
		return ret;
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}