최's 먹공로그
BOJ2644 촌수계산 본문
<Solution>
1. 사람 수 만큼의 N by N map에 촌수가 연결된 번호들을 1로 표시
2. 계산해야 되는 촌수의 노드 중 앞번호 먼저 탐색 시작
3. 연결된 다른 노드가 있는지 보고 해당 노드를 다시 탐색 반복
4. 노드를 타고 들어갈 때 마다 cnt++
5. for i가 계산해야 되는 촌수의 뒤번호랑 일치되면 flag 표시 해줘서 나머지 탐색에서 다 return
6. 백트레킹 해서 찾아야되는 경우 고려(cnt, visit_node 복구)
<Source Code>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ2644_촌수계산 {
static int[][] map;
static int[] visit_node;
static int cnt;
static int map_size;
static int target_numder;
static int flag = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), "");
int N = Integer.parseInt(st.nextToken());
map_size = N;
map = new int[N + 1][N + 1];
visit_node = new int[N + 1];
st = new StringTokenizer(br.readLine(), " ");
int f = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
target_numder = s;
st = new StringTokenizer(br.readLine(), "");
int M = Integer.parseInt(st.nextToken());
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
map[x][y] = 1;
map[y][x] = 1;
}
dfs(f);
if(flag == 1)
System.out.print(cnt);
else
System.out.print(-1);
}
public static void dfs(int f) {
visit_node[f] = 1;
for(int i = 1; i <= map_size; i++) {
if(flag == 1) // 이미 촌수 계산이 완료된 상태
return;
if(visit_node[i] == 1 || map[f][i] == 0)
continue;
cnt++;
if(i == target_numder) { // 촌수 계산해야 되는 노드를 찾았다는건 더 볼필요 없으니깐 flag 변경
flag = 1;
return;
}
dfs(i);
if(flag == 1) // 백트레킹으로 왔을 때 촌수 계산이 완료된 상태면 더 볼필요 x
return;
// 백트레킹으로 왔을 때 원래 값으로 만들기
cnt--;
visit_node[i] = 0;
}
}
}
좀 드럽긴 한데 일단... 백트레킹 되는 경우에도 flag == 1 경우를 고려해야되는 걸 빼먹어서 좀 걸림... dfs 디버깅 너무 어려워...
'APS' 카테고리의 다른 글
BOJ1697 숨바꼭질 (0) | 2022.06.12 |
---|---|
BOJ7569 토마토 (0) | 2022.06.06 |
BOJ2667 단지번호붙이기 (0) | 2022.06.05 |
BOJ2606 바이러스 (0) | 2022.06.03 |
BOJ2178 미로탐색 (0) | 2022.05.22 |