[Algorithm] ๐ฅ๋ฐฑ์ค ์์๋ฌผ ํผํ๊ธฐ
0. ๋ฌธ์
์ฝ๋ ์ค์ฝ ์ฝ๋๋ฏธ๋์ 8์ธต์ ํ์๋ค์ด 3๋ผ์ ์์ฌ๋ฅผ ํด๊ฒฐํ๋ ๊ณต๊ฐ์ด๋ค. ๊ทธ๋ฌ๋ ๋ช๋ช ๋น์์ฌ์ ์ธ ํ์๋ค์ ๋งํ์ผ๋ก ์์๋ฌผ์ด ํต๋ก ์ค๊ฐ ์ค๊ฐ์ ๋จ์ด์ ธ ์๋ค. ์ด๋ฌํ ์์๋ฌผ๋ค์ ๊ทผ์ฒ์ ์๋ ๊ฒ๋ผ๋ฆฌ ๋ญ์น๊ฒ ๋ผ์ ํฐ ์์๋ฌผ ์ฐ๋ ๊ธฐ๊ฐ ๋๋ค.
์ด ๋ฌธ์ ๋ฅผ ์ถ์ ํ ์ ์๋์ ๊ฐ์ธ์ ์ผ๋ก ์ด๋ฌํ ์์๋ฌผ์ ์ค๋ดํ์ ๋ฌปํ๋ ๊ฒ์ ์ ๋ง ์ง์ ์ผ๋ก ์ซ์ดํ๋ค. ์ฐธ๊ณ ๋ก ์ฐ๋ฆฌ๊ฐ ๊ตฌํด์ผ ํ ๋ต์ ์ด ๋ฌธ์ ๋ฅผ ๋ธ ์กฐ๊ต๋ฅผ ๋ง์ถ๋ ๊ฒ์ด ์๋๋ค.
ํต๋ก์ ๋จ์ด์ง ์์๋ฌผ์ ํผํด๊ฐ๊ธฐ๋ ์ฌ์ด ์ผ์ด ์๋๋ค. ๋ฐ๋ผ์ ์ ์๋์ ๋จ์ด์ง ์์๋ฌผ ์ค์ ์ ์ผ ํฐ ์์๋ฌผ๋ง์ ํผํด ๊ฐ๋ ค๊ณ ํ๋ค.
์ ์๋์ ๋์ ์ ์ผ ํฐ ์์๋ฌผ์ ํฌ๊ธฐ๋ฅผ ๊ตฌํด์ โ10ra"๋ฅผ ์ธ์น์ง ์๊ฒ ๋์์ฃผ์.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ํต๋ก์ ์ธ๋ก ๊ธธ์ด N(1 โค N โค 100)๊ณผ ๊ฐ๋ก ๊ธธ์ด M(1 โค M โค 100) ๊ทธ๋ฆฌ๊ณ ์์๋ฌผ ์ฐ๋ ๊ธฐ์ ๊ฐ์ K(1 โค K โค 10,000)์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ๋ค์ K๊ฐ์ ์ค์ ์์๋ฌผ์ด ๋จ์ด์ง ์ขํ (r, c)๊ฐ ์ฃผ์ด์ง๋ค.
์ขํ (r, c)์ r์ ์์์๋ถํฐ, c๋ ์ผ์ชฝ์์๋ถํฐ๊ฐ ๊ธฐ์ค์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์์๋ฌผ ์ค ๊ฐ์ฅ ํฐ ์์๋ฌผ์ ํฌ๊ธฐ๋ฅผ ์ถ๋ ฅํ๋ผ.
1. ์์ด๋์ด
๐ก DFS
๐ก ์์๋ฌผ ์ฐ๋ ๊ธฐ๊ฐ ์๋ ๊ณณ์ ํ์ํจ
๐ก ์ ์ฒด ๋ฐฐ์ด์์ ์ฐ๋ ๊ธฐ๊ฐ ์๋ ๊ณณ์ ์ ํํ๊ณ ์ํ์ข์ฐ์๋ ์ฐ๋ ๊ธฐ๊ฐ ์์ผ๋ฉด count๋ฅผ ํ๊ณ ์ฐ๋ ๊ธฐ๊ฐ ์๋ ์๋ฆฌ๋ก ๋์ด๊ฐ
๐ก ์ฐ๋ ๊ธฐ๊ฐ ์๋ ์๋ฆฌ๊ฐ ์ด์ด์ง์ง ์๋๋ค๋ฉด ๋ค์ ๋์์ ์ ์ฒด ๋ฐฐ์ด์ ํ์ํ์ฌ ์ฐ๋ ๊ธฐ๊ฐ ์๋ ๊ณณ์ ์ฐพ์๋ด์ด ์์ ์ฝ๋๋ฅผ ๋ฐ๋ณตํจ
2. ํต์ฌ ํ์ด
1) ์์๋ฌผ ์ฐ๋ ๊ธฐ๊ฐ ์๋ ๊ณณ์ ํ์ํจ
for(int i=0; i<k; i++) {
s = br.readLine().split(" ");
map[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = trash;
}
2) ์ ์ฒด ๋ฐฐ์ด์์ ์ฐ๋ ๊ธฐ๊ฐ ์๋ ๊ณณ์ ์ ํํ๊ณ ์ํ์ข์ฐ์๋ ์ฐ๋ ๊ธฐ๊ฐ ์์ผ๋ฉด count๋ฅผ ํ๊ณ ์ฐ๋ ๊ธฐ๊ฐ ์๋ ์๋ฆฌ๋ก ๋์ด๊ฐ
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 1 || ny < 1 || nx>=n+1 || ny>=m+1)
continue;
if(!visited[nx][ny] && map[nx][ny] == trash) {
visited[nx][ny] = true;
dfs(nx,ny);
}
}
3) ์ฐ๋ ๊ธฐ๊ฐ ์๋ ์๋ฆฌ๊ฐ ์ด์ด์ง์ง ์๋๋ค๋ฉด ๋ค์ ๋์์ ์ ์ฒด ๋ฐฐ์ด์ ํ์ํ์ฌ ์ฐ๋ ๊ธฐ๊ฐ ์๋ ๊ณณ์ ์ฐพ์๋ด์ด ์์ ์ฝ๋๋ฅผ ๋ฐ๋ณตํจ
for(int i=1; i<n+1; i++) {
for(int j=1; j<m+1; j++) {
if(map[i][j] == trash) {
visited[i][j] = true;
dfs(i,j);
max = Math.max(count, max);
count = 0;
}
}
}
3. ์ฝ๋
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;
import java.util.ArrayList;
public class Bruteforce_7 {
static final int trash = 1;
static int n,m,k, count = 0;
static int[][] map;
static boolean[][] visited;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
k = Integer.parseInt(s[2]);
map = new int[n+1][m+1];
visited = new boolean[n+1][m+1];
for(int i=0; i<k; i++) {
s = br.readLine().split(" ");
map[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = trash;
}
int max = 0;
for(int i=1; i<n+1; i++) {
for(int j=1; j<m+1; j++) {
if(map[i][j] == trash) {
visited[i][j] = true;
dfs(i,j);
max = Math.max(count, max);
count = 0;
}
}
}
System.out.println(max);
}
public static void dfs(int x, int y) {
count++;
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 1 || ny < 1 || nx>=n+1 || ny>=m+1)
continue;
if(!visited[nx][ny] && map[nx][ny] == trash) {
visited[nx][ny] = true;
dfs(nx,ny);
}
}
}
}
4. ๊ฒฐ๊ณผ
์ฑ๊ณตโจ
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐ฅ๋ฐฑ์ค ์์๋ฌผ ํผํ๊ธฐ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-์์๋ฌผ-ํผํ๊ธฐ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค