๋ฌธ์ (Gold 4)
https://www.acmicpc.net/problem/14466
14466๋ฒ: ์๊ฐ ๊ธธ์ ๊ฑด๋๊ฐ ์ด์ 6
์ฒซ ์ค์ N, K, R์ด ์ฃผ์ด์ง๋ค. ๋ค์ R์ค์๋ ํ ์ค์ ํ๋์ฉ ๊ธธ์ด ์ฃผ์ด์ง๋ค. ๊ธธ์ ์ํ์ข์ฐ๋ก ์ธ์ ํ ๋ ๋ชฉ์ด์ง๋ฅผ ์๊ณ , r c r′ c′์ ํํ (ํ, ์ด, ํ, ์ด)๋ก ์ฃผ์ด์ง๋ค. ๊ฐ ์๋ 1 ์ด์ N ์ดํ์ด๋ค.
www.acmicpc.net
ํ์ด
๋ฌธ์ ํด์
1. ์ผ๋ฐ ๋ชฉ์ด์ง ์ฌ์ด๋ ์ํ์ข์ฐ ๋ชจ๋ ์์ง์ผ ์ ์๋ค.
2. ์ค๊ฐ์ ๋ค๋ฆฌ๊ฐ ์๋ค๋ฉด, ๋ค๋ฆฌ๋ฅผ ๊ผญ ๊ฑด๋์ผ ํ๋ค.
์ฆ, ์(2,2)๋ ์(2,3)๊น์ง ๋ค๋ฆฌ๋ฅผ ๊ฑด๋์ผํ ์๋ ์์ง๋ง, ๊ทธ ๊ธธ์ ํํผํด ํ์ ํ์ดํ ๊ธธ๋ก ๊ฐ ์ ์๋ค.
์(3,3)์ ๋ค๋ฅธ ๋ชฉ์ด์ง์ ๊ฐ๋ ค๋ฉด ๋ฌด์กฐ๊ฑด ๋ค๋ฆฌ๋ฅผ ๊ฑด๋์ผ ํ๋ฏ๋ก, ๋ชจ๋ ์์ ์ ํจํ ์์ด ๋๋ค.
ํ์ด
1. ์๊ฐ ์๋ ๊ณณ์ ์ค์ฌ์ผ๋ก BFS ํ์์ ํ์ฌ, ์์ญ์ ํ์ํ๋ค.
2. ๋ชจ๋ ์๊ฐ ์๋ ๊ณณ์ ์์ญ์ ํ์
3. ํ์ฌ ์์ ๊ทธ ๋ค์ ์๋ค์ ๋น๊ตํ๋ฉฐ ๋ค๋ฅธ ์์ญ์ ์๋ค๋ฉด ๊ฒฐ๊ณผ๊ฐ์ +1 ํ๋ค.
์ฝ๋
package graphTraversal;
import java.io.*;
import java.util.*;
public class BOJ_14466_์๊ฐ๊ธธ์๊ฑด๋๊ฐ์ด์ 6 {
static int[] di = {-1, 0, 1, 0};
static int[] dj = {0, -1, 0, 1};
static int N,K,R;
static List<int[]> bridge; // ๋ค๋ฆฌ์ ์ ๋ณด๋ฅผ ์ ์ฅ
static List<int[]> cowPos; // ์์ ์์น์ ์ ๋ณด๋ฅผ ์ ์ฅ
static int[][] map; // ์์ญ์ ์ ์ฅ
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
bridge = new ArrayList<>();
cowPos = new ArrayList<>();
map = new int[N][N];
for(int i =0 ; i < N ; i++) Arrays.fill(map[i], -1);
for(int i =0 ; i < R ; i++){
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken())-1;
int r1 = Integer.parseInt(st.nextToken())-1;
int c1 = Integer.parseInt(st.nextToken())-1;
bridge.add(new int[]{r, c, r1, c1});
}
for(int i =0 ; i < K ; i++){
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken())-1;
cowPos.add(new int[]{r, c});
}
for(int i = 0 ; i < K ; i++){ // ์๊ฐ ์๋ ์์น๋ฅผ ๊ธฐ์ค์ผ๋ก ํ์ ์์
if(map[cowPos.get(i)[0]][cowPos.get(i)[1]] == -1){ // ์ด๋ฏธ ํ์์ด ๋ ๊ณณ์ด๋ผ๋ฉด pass
findWay(cowPos.get(i), i);
}
}
int cnt = 0;
for(int i =0 ; i < K-1 ; i++){
for(int j = i+1 ; j < K ; j++){
if(map[cowPos.get(i)[0]][cowPos.get(i)[1]] != map[cowPos.get(j)[0]][cowPos.get(j)[1]]) cnt ++; // ์์ญ์ด ๋ค๋ฅธ ๊ณณ์ ์์ผ๋ฉด ๊ธธ์ ๊ฑด๋์ผ ํ๋ฏ๋ก cnt++
}
}
System.out.println(cnt);
}
private static void findWay(int[] c, int area) {
boolean[][] visited = new boolean[N][N];
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{c[0], c[1]});
visited[c[0]][c[1]] = true;
map[c[0]][c[1]] = area;
while(!q.isEmpty()){
int i = q.peek()[0];
int j = q.poll()[1];
next:for(int d = 0 ; d < 4 ; d++){
int ni = i+di[d];
int nj = j+dj[d];
if(0<=ni&&ni<N && 0<=nj&&nj<N && !visited[ni][nj]){
for(int[] b: bridge){ // ๋ ์ฌ์ด์ ๋ค๋ฆฌ๊ฐ ์๋์ง ํ์ธ
if(b[0]==i&&b[1]==j && b[2]==ni&&b[3]==nj) continue next;
if(b[2]==i&&b[3]==j && b[0]==ni&&b[1]==nj) continue next;
}
q.offer(new int[]{ni, nj});
visited[ni][nj] = true;
map[ni][nj] = area; // ํ์ํ ์๋ฆฌ์ ์์ญ์ ํ์
}
}
}
}
}
'๐ ์๊ณ ๋ฆฌ์ฆ > GraphTraversal' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[LeetCode] 802. Find Eventual Safe States (ํด์, kotlin ํ์ด) (0) | 2023.07.12 |
---|---|
[๋ฐฑ์ค] 11967๋ฒ: ๋ถ์ผ๊ธฐ (JAVA) (0) | 2022.04.04 |
[๋ฐฑ์ค] 3184๋ฒ ์ (Java) (0) | 2022.02.16 |
[๋ฐฑ์ค] 5427๋ฒ ๋ถ (Java) (0) | 2022.02.08 |
[๋ฐฑ์ค] 2606๋ฒ ๋ฐ์ด๋ฌ์ค (Java) (0) | 2021.08.24 |