: 안전영역을 구하는 문제이다. 2차원 배열의 형태가 주어졌을 때, 특정 수 이상의 범위로 안전범위를 지정하여 그 최대 갯수를 구하는 문제이다.
제일 먼저 입력을 받으면서 모든 원소의 값을 list 로 저장해주어야 한다. (중복을 허용하지 않기 위해 List 사용)
static int N;
static int[][] area;
static List<Integer> list = new ArrayList<>();
static void input()
{
N = scan.nextInt();
area = new int[N+1][N+1];
for(int i=1; i<=N; i++)
{
for(int j=1; j<=N; j++)
{
area[i][j] = scan.nextInt();
if(!list.contains(area[i][j])) list.add(area[i][j]);
}
}
}
순회
: 그 후, 모든 영역을 탐색하며 해당 지역을 방문하지 않았고 특정 원소의 길이보다 크다면 dfs 를 통해 그 지역을 모두 체크해서 안전범위를 체크해주어야 한다.
list 에 들어있는 값을 기준으로 안전 범위를 모두 탐색하고 최대 값을 갱신한다.
static void pro()
{
int max = Integer.MIN_VALUE;
for(int k : list)
{
int cnt = 0;
visit = new boolean[N+1][N+1]; // 방문여부
for(int i=1; i<=N; i++)
{
for(int j=1; j<=N; j++)
{
if(area[i][j] >= k && !visit[i][j])
{
cnt++;
dfs(i,j, k);
}
}
}
max = Math.max(max, cnt);
}
}
dfs
: 순회를 하는 과정까지 코드로 작성하였으면 dfs 로 인접한 범위를 모두 탐색한다.
처음 dfs 를 실행했을 때 방문 여부를 체크하는 visit 을 true 로 선언해줘야 중복 실행을 방지할 수 있다.
그 후 상하좌우로 이동할 수 있는 지 여부를 확인한다.
dir 은 상하좌우의 좌표를 의미한다. 그리고 3가지 예외처리를 진행해 주어야 한다.
1. 지도를 벗어나는 경우
2. 안전 지역이 아닌 경우
3. 이미 방문한 경우
이 3가지 경우를 벗어난 좌표는 재 탐색을 진행한다. dfs(nx, ny, k)
이 과정을 통해 인접한 곳을 모두 확인하고 안전범위를 확립할 수 있다.
// 상하좌우로 한칸씩 이동한 좌표를 비교하기 위함
static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
// x, y 를 갈 수 있다는 걸 알고 방문한 상태
static void dfs(int x, int y, int k)
{
// 방문 표기
visit[x][y] = true;
for(int i=0; i<4; i++)
{
int nx = x + dir[i][0];
int ny = y + dir[i][1];
// 지도를 벗어나는 경우
if(nx<0 || ny<0 || nx>N || ny>N) continue;
// 안전 지역이 아닌 경우, 5미만
if(area[nx][ny]<k) continue;
// 이미 방문했으면 pass
if(visit[nx][ny]) continue;
dfs(nx, ny, k);
}
}
전체 코드
static FastReader scan = new FastReader();
static int N;
static List<Integer> list = new ArrayList<>();
static boolean[][] visit;
static int[][] area;
static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 상하좌우로 한칸씩 이동한 좌표를 비교하기 위함
static void input()
{
N = scan.nextInt();
area = new int[N+1][N+1];
for(int i=1; i<=N; i++)
{
for(int j=1; j<=N; j++)
{
area[i][j] = scan.nextInt();
if(!list.contains(area[i][j])) list.add(area[i][j]);
}
}
}
static void pro()
{
int max = Integer.MIN_VALUE;
for(int k : list)
{
int cnt = 0;
visit = new boolean[N+1][N+1]; // 방문여부
for(int i=1; i<=N; i++)
{
for(int j=1; j<=N; j++)
{
if(area[i][j] >= k && !visit[i][j])
{
cnt++;
dfs(i,j, k);
}
}
}
max = Math.max(max, cnt);
}
System.out.println(max);
}
// x, y 를 갈 수 있다는 걸 알고 방문한 상태
static void dfs(int x, int y, int k)
{
// 방문 표기
visit[x][y] = true;
for(int i=0; i<4; i++)
{
int nx = x + dir[i][0];
int ny = y + dir[i][1];
// 지도를 벗어나는 경우
if(nx<0 || ny<0 || nx>N || ny>N) continue;
// 안전 지역이 아닌 경우, 5미만
if(area[nx][ny]<k) continue;
// 이미 방문했으면 pass
if(visit[nx][ny]) continue;
dfs(nx, ny, k);
}
}
public static void main(String[] args)
{
input();
pro();
}
급하게 조사하고 정리하다보니 부족하거나 틀린 내용이 있을 수도 있는데 댓글로 달아주시면 감사하겠습니다!