๐ ๋ฌธ์
https://www.acmicpc.net/problem/2468
๋ฌธ์
์ฌ๋๋ฐฉ์ฌ์ฒญ์์๋ ๋ง์ ๋น๊ฐ ๋ด๋ฆฌ๋ ์ฅ๋ง์ฒ ์ ๋๋นํด์ ๋ค์๊ณผ ๊ฐ์ ์ผ์ ๊ณํํ๊ณ ์๋ค. ๋จผ์ ์ด๋ค ์ง์ญ์ ๋์ด ์ ๋ณด๋ฅผ ํ์ ํ๋ค. ๊ทธ ๋ค์์ ๊ทธ ์ง์ญ์ ๋ง์ ๋น๊ฐ ๋ด๋ ธ์ ๋ ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์์ ํ ์์ญ์ด ์ต๋๋ก ๋ช ๊ฐ๊ฐ ๋ง๋ค์ด ์ง๋ ์ง๋ฅผ ์กฐ์ฌํ๋ ค๊ณ ํ๋ค. ์ด๋, ๋ฌธ์ ๋ฅผ ๊ฐ๋จํ๊ฒ ํ๊ธฐ ์ํ์ฌ, ์ฅ๋ง์ฒ ์ ๋ด๋ฆฌ๋ ๋น์ ์์ ๋ฐ๋ผ ์ผ์ ํ ๋์ด ์ดํ์ ๋ชจ๋ ์ง์ ์ ๋ฌผ์ ์ ๊ธด๋ค๊ณ ๊ฐ์ ํ๋ค.
์ด๋ค ์ง์ญ์ ๋์ด ์ ๋ณด๋ ํ๊ณผ ์ด์ ํฌ๊ธฐ๊ฐ ๊ฐ๊ฐ N์ธ 2์ฐจ์ ๋ฐฐ์ด ํํ๋ก ์ฃผ์ด์ง๋ฉฐ ๋ฐฐ์ด์ ๊ฐ ์์๋ ํด๋น ์ง์ ์ ๋์ด๋ฅผ ํ์ํ๋ ์์ฐ์์ด๋ค. ์๋ฅผ ๋ค์ด, ๋ค์์ N=5์ธ ์ง์ญ์ ๋์ด ์ ๋ณด์ด๋ค.
6 | 8 | 2 | 6 | 2 |
3 | 2 | 3 | 4 | 6 |
6 | 7 | 3 | 3 | 2 |
7 | 2 | 5 | 3 | 6 |
8 | 9 | 5 | 2 | 7 |
์ด์ ์์ ๊ฐ์ ์ง์ญ์ ๋ง์ ๋น๊ฐ ๋ด๋ ค์ ๋์ด๊ฐ 4 ์ดํ์ธ ๋ชจ๋ ์ง์ ์ด ๋ฌผ์ ์ ๊ฒผ๋ค๊ณ ํ์. ์ด ๊ฒฝ์ฐ์ ๋ฌผ์ ์ ๊ธฐ๋ ์ง์ ์ ํ์์ผ๋ก ํ์ํ๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
6 | 8 | 2 | 6 | 2 |
3 | 2 | 3 | 4 | 6 |
6 | 7 | 3 | 3 | 2 |
7 | 2 | 5 | 3 | 6 |
8 | 9 | 5 | 2 | 7 |
๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์์ ํ ์์ญ์ด๋ผ ํจ์ ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์ง์ ๋ค์ด ์, ์๋, ์ค๋ฅธ์ชฝ ํน์ ์ผ์ชฝ์ผ๋ก ์ธ์ ํด ์์ผ๋ฉฐ ๊ทธ ํฌ๊ธฐ๊ฐ ์ต๋์ธ ์์ญ์ ๋งํ๋ค. ์์ ๊ฒฝ์ฐ์์ ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์์ ํ ์์ญ์ 5๊ฐ๊ฐ ๋๋ค(๊ผญ์ง์ ์ผ๋ก๋ง ๋ถ์ด ์๋ ๋ ์ง์ ์ ์ธ์ ํ์ง ์๋๋ค๊ณ ์ทจ๊ธํ๋ค).
๋ํ ์์ ๊ฐ์ ์ง์ญ์์ ๋์ด๊ฐ 6์ดํ์ธ ์ง์ ์ ๋ชจ๋ ์ ๊ธฐ๊ฒ ๋ง๋๋ ๋ง์ ๋น๊ฐ ๋ด๋ฆฌ๋ฉด ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์์ ํ ์์ญ์ ์๋ ๊ทธ๋ฆผ์์์ ๊ฐ์ด ๋ค ๊ฐ๊ฐ ๋จ์ ํ์ธํ ์ ์๋ค.
6 | 8 | 2 | 6 | 2 |
3 | 2 | 3 | 4 | 6 |
6 | 7 | 3 | 3 | 2 |
7 | 2 | 5 | 3 | 6 |
8 | 9 | 5 | 2 | 7 |
์ด์ ๊ฐ์ด ์ฅ๋ง์ฒ ์ ๋ด๋ฆฌ๋ ๋น์ ์์ ๋ฐ๋ผ์ ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์์ ํ ์์ญ์ ๊ฐ์๋ ๋ค๋ฅด๊ฒ ๋๋ค. ์์ ์์ ๊ฐ์ ์ง์ญ์์ ๋ด๋ฆฌ๋ ๋น์ ์์ ๋ฐ๋ฅธ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ๋ค ์กฐ์ฌํด ๋ณด๋ฉด ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์์ ํ ์์ญ์ ๊ฐ์ ์ค์์ ์ต๋์ธ ๊ฒฝ์ฐ๋ 5์์ ์ ์ ์๋ค.
์ด๋ค ์ง์ญ์ ๋์ด ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, ์ฅ๋ง์ฒ ์ ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์์ ํ ์์ญ์ ์ต๋ ๊ฐ์๋ฅผ ๊ณ์ฐํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ์ด๋ค ์ง์ญ์ ๋ํ๋ด๋ 2์ฐจ์ ๋ฐฐ์ด์ ํ๊ณผ ์ด์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ N์ด ์ ๋ ฅ๋๋ค. N์ 2 ์ด์ 100 ์ดํ์ ์ ์์ด๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ๊ฐ ์ค์๋ 2์ฐจ์ ๋ฐฐ์ด์ ์ฒซ ๋ฒ์งธ ํ๋ถํฐ N๋ฒ์งธ ํ๊น์ง ์์๋๋ก ํ ํ์ฉ ๋์ด ์ ๋ณด๊ฐ ์ ๋ ฅ๋๋ค. ๊ฐ ์ค์๋ ๊ฐ ํ์ ์ฒซ ๋ฒ์งธ ์ด๋ถํฐ N๋ฒ์งธ ์ด๊น์ง N๊ฐ์ ๋์ด ์ ๋ณด๋ฅผ ๋ํ๋ด๋ ์์ฐ์๊ฐ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์ ๋ ฅ๋๋ค. ๋์ด๋ 1์ด์ 100 ์ดํ์ ์ ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ฅ๋ง์ฒ ์ ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์์ ํ ์์ญ์ ์ต๋ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
๋ ธํธ
์๋ฌด ์ง์ญ๋ ๋ฌผ์ ์ ๊ธฐ์ง ์์ ์๋ ์๋ค.
โ๏ธ ํ์ด
๋น๊ฐ ์ ๊ฒ ๋ด๋ ค ์๋ฌด ์ง์ญ๋ ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ๊ฒฝ์ฐ๋ฅผ ๊ฒฐ๊ณผ ๋ณ์์ ์ด๊ธฐ๊ฐ์ผ๋ก ์ค์ ํด๋๋ค.
๐ก ์๋ฌด ์ง์ญ๋ ์ ๊ธฐ์ง ์์๋ค๋ฉด, ์ ์ฒด ์งํ์ ๋ญ์น ๋ฉ์ด๋ฆฌ ํ๋๊ฐ ์์ ์ง๋๊ฐ ๋๋ ๊ฒ์ด๋ฏ๋ก ์ด๊ธฐ๊ฐ์ 1์ด๋ค.
๋์ด๊ฐ 1์ธ ๊ฒฝ์ฐ๋ถํฐ ์ต๊ณ ๋์ด๊น์ง ๋น์ ์ ๊ธธ ๋์ด๋ฅผ ๋์ฌ๊ฐ๋ฉด์ ์์ ์ง๋๋ฅผ ํ์ํ๋ค.
๋งค ๋ฃจํ๋ง๋ค ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ๋ฐฐ์ด์ ์๋ก ๋ง๋ค๋ฉด์ ์ ์ฒด ์งํ์ ์์ ํ์์ ํ๊ณ , ์นด์ดํ ๋ ์์ ์ง๋ ๊ฐ์๋ฅผ ๊ฒฐ๊ณผ ๋ณ์์ ๊ฐ๊ณผ ๋น๊ตํ์ฌ ๋ ํฐ ๊ฐ์ผ๋ก ์ ๋ฐ์ดํธํ๋ค.
๋ชจ๋ ๋์ด๋ฅผ ํ์ํ๊ณ ๋ ๋ค ๋ง์ง๋ง ๊ฒฐ๊ณผ ๋ณ์ ๊ฐ์ ์ถ๋ ฅํ๋ค.
๐โ๏ธ ์๊ฒฌ
์ฒ์์ ๋ฌธ์ ์ดํดํ๋๋ฐ ์ค๋ ๊ฑธ๋ ธ๋ค. ์ด๊ฒ ๋น์ต ๋ฌด์จ ๋ง์ธ์ง;;;
์ฅ๋ง์ฒ ์ ๋ฌผ์ ์ ๊ธฐ์ง ์๋ ์ต๋ ๊ฐ์๋ฅผ ๊ตฌํ๋ ค๋ฉด ์ ๊ธฐ๋ ๋์ด๋ฅผ ์์์ผํ์ง ์๋? ํ๋๋ ๊ทธ๋ฅ ๋ชจ๋ ๋์ด๋ฅผ ์กฐ์ฌํ๋ ๊ฑฐ์๋ค.
BFS๋ก ํ์ด๋ ๋์ง๋ง, DFS๋ฅผ ๋๋ฌด ์์จ๋ณด๋ ๊ฒ ๊ฐ์์ ์ผ๋ถ๋ฌ DFS๋ก ํ์๋ค.
๐ป ์์ค์ฝ๋: ์๋ฐ(Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//DFS
public class Main_๋ฐฑ์ค_2468_์์ ์์ญ_์ค๋ฒ1 {
static int N, result=1;
static int[][] map;
static boolean[][] visited;
static int[] dr = {1,-1,0,0};
static int[] dc = {0,0,1,-1};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
visited = new boolean[N][N];
int max = 0; //์งํ์ ์ต๊ณ ๋์ด
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j]>max) max = map[i][j];
}
}//input
for (int h = 1; h <= max; h++) {
init(); //visited๋ฐฐ์ด ์ด๊ธฐํ
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(map[i][j]>h && !visited[i][j]) {//์์ ์ง๋ ๋ฐ๊ฒฌ
cnt++;
dfs(i,j,h);
}
}
}
result = Math.max(cnt, result);
}
System.out.println(result);
}//end of main
private static void init() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
visited[i][j]=false;
}
}
}//end of init
private static void dfs(int r, int c, int h) {
visited[r][c]=true;
for (int i = 0; i < 4; i++) {
int nr = r+dr[i];
int nc = c+dc[i];
// exception
if(nr<0||nc<0||nr>=N||nc>=N||
//๋ฌผ์ ์ ๊ธฐ๊ฑฐ๋ ์ด๋ฏธ ํ์ธํ ๊ณณ์ด๋ฉด ์ฒดํฌํ์ง ์๋๋ค
map[nr][nc]<=h||visited[nr][nc]) continue;
dfs(nr,nc,h);
}
}//end of dfs
private static void bfs(int r, int c, int h) {
Queue<int[]> queue = new LinkedList<>();
visited[r][c]=true;
queue.offer(new int[]{r,c});
while(queue.size()>0){
int[] cur = queue.poll();
for (int i = 0; i < 4; i++) {
int nr = cur[0]+dr[i];
int nc = cur[1]+dc[i];
// exception
if(nr<0||nc<0||nr>=N||nc>=N||
//๋ฌผ์ ์ ๊ธฐ๊ฑฐ๋ ์ด๋ฏธ ํ์ธํ ๊ณณ์ด๋ฉด ์ฒดํฌํ์ง ์๋๋ค
map[nr][nc]<=h||visited[nr][nc]) continue;
visited[nr][nc] = true;
queue.offer(new int[]{nr,nc});
}
}
}//end of bfs
}//end of class
๐ ๐ ๐
๏ผฐ๏ฝ๏ฝ๏ฝ๏ฝ ๏ฝ ๏ผข๏ฝ ๏ผณ๏ผก๏ผน
๐๐ฉ๐ข๐ฏ๐ฌ๐ด ๐ง๐ฐ๐ณ ๐ณ๐ฆ๐ข๐ฅ๐ช๐ฏ๐จ