[백준/Java] 23835번 어떤 우유의 배달목록 (Easy)

 

 

문제풀이

이 문제는 DFS(깊이 우선 탐색)로 풀어야 한다.

BFS로만 풀다가 시간을 다 날렸다 ... ^^

사실 재귀 울렁증이 있는 나는 그래프 문제가 나오면 BFS로 풀기 때문에 계속 BFS로 붙잡으면서 답을 못 찾다가

알고리즘 분류를 봤는데 DFS로 풀으라고 되어있었고, 아차 싶었다..

좀 더 생각해봤으면 이건 BFS가 아니라 DFS로 풀어야한다는걸 알았을텐데 아직 부족한다보다.

 

public class Main {
    static int N;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    static int[] cnt;

1. staic 변수를 선언해준다.

N은 방의 개수를 담을 변수이다.

list는 인접리스트로 저장하기 위해 2차원 ArrayList로 만든다.

cnt는 우유의 개수를 저장하기 위한 정수형 배열이다.

 

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    StringBuilder sb = new StringBuilder();

    N = Integer.parseInt(bf.readLine());
    cnt = new int[N+1];

2. 출력 값을 담기위해 StringBuilder sb를 생성한다.

그리고 방의 개수 N을 입력 받고,

cnt의 크기는 N+1로 만든다.(인덱스 0은 사용하지 않음.)

 

for(int i=0; i<=N; i++) {
    list.add(new ArrayList<Integer>());
}

3. 2차원 ArrayList를 초기화한다.

 

[ArrayList의 각 인덱스에 새로운 빈 ArrayList를 추가해서 각 인덱스에

데이터를 넣을 수 있도록 미리 공간을 확보하기 위한 작업]

 

for(int i=0; i<N-1; i++) {
    st = new StringTokenizer(bf.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    list.get(a).add(b);
    list.get(b).add(a);
}

4. 그래프의 인접리스트를 구성한다.

양방향이기 때문에,

정점 a의 인접리스트에 정점 b를 추가하고,

정점 b의 인접리스트에 정점 a를 추가한다.

 

int Q = Integer.parseInt(bf.readLine());

5. 쿼리의 개수 Q를 입력받는다.

 

for(int i=0; i<Q; i++) {
    st = new StringTokenizer(bf.readLine());
    int t = Integer.parseInt(st.nextToken());

    int[] tmpCnt = new int[N+1];
    boolean[] visited = new boolean[N+1];

    if(t == 1) {
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        visited[start] = true;
        bfs(start, end, 0, visited, tmpCnt);
    }else {
        int num = Integer.parseInt(st.nextToken());
        sb.append(cnt[num]).append("\n");
    }
}

6. 쿼리의 개수 Q만큼 반복한다.

t를 입력 받는다. (t는 1 or 2)

그리고 우유의 개수를 카운트할 임시 count 배열을 생성하고, 방문처리할 boolean 배열도 생성한다.

 

if(t == 1) {
    int start = Integer.parseInt(st.nextToken());
    int end = Integer.parseInt(st.nextToken());
    visited[start] = true;
    bfs(start, end, 0, visited, tmpCnt);
}

그리고 t가 1일 때, 2일 때에 따라 처리를 다르게 해야한다.

만약 t = 1 이라면,

start와 end 값을 받고, 방문처리를 한다.

그리고 bfs 함수를 실행한다. 이 때 인자로는

start : 시작 값,

end : 종료 값,

0 : 우유 개수,

visited: 방문 배열,

tmpCnt: 우유 개수 카운트할 배열 을 가져간다.

 

else {
    int num = Integer.parseInt(st.nextToken());
    sb.append(cnt[num]).append("\n");
}

만약 t가 2라면,

num을 입력받고,

cnt 배열에서 인덱스 num에 해당하는 값을 가져와 sb에 저장한다.

 

public static void bfs(int start, int end, int count, boolean[] visited, int[] tmpCnt) {
    if(start == end) {
        for(int i=1; i<=N; i++) {
            if(visited[i]) {
                cnt[i] += tmpCnt[i];
            }
        }
        return;
    }

    for(int next: list.get(start)) {
        if(!visited[next]) {
            visited[next] = true;
            tmpCnt[next] += count+1;
            bfs(next, end, count+1, visited, tmpCnt);
            visited[next] = false;
        }
    }
    return;
}

7. bfs(사실 dfs인데 함수명 수정 안 했다.) 함수를 실행한다.

 

if(start == end) {
    for(int i=1; i<=N; i++) {
        if(visited[i]) {
            cnt[i] += tmpCnt[i];
        }
    }
return;
}

만약 현재 정점인 start와 도착 정점인 end가 같다면 목표 지점에 도달한 것이다.

1~N까지 전체 정점을 순환하며 해당 정점이 현재 경로를 방문했다면 임시 배열인 tmpCnt에 저장된 값을 배열 cnt에 더한다.

목표지점에 도달했기 때문에 더 이상 재귀를 하지 않고 함수 실행을 종료한다.

 

for(int next: list.get(start)) {
    if(!visited[next]) {
        visited[next] = true;
        tmpCnt[next] += count+1;
        bfs(next, end, count+1, visited, tmpCnt);
        visited[next] = false;
    }
}
return;

현재 정점인 start에 인접한 모든 정점 next에 대해 반복한다.

 

 if(!visited[next]) {
        visited[next] = true;
        tmpCnt[next] += count+1;

만약 인접 정점인 next에 방문하지 않았다면 방문처리를 하고,

배열 tmpCnt에 현재까지 배달한 우유의 개수에 1을 더한 값을 누적한다. (지금 보니 count가 아니라 직관적으로 milk라고 변수명을 짓는게 좋겠다. 변수 이름의 중요성🥛☺️)

 

bfs(next, end, count+1, visited, tmpCnt); 

재귀를 활용해 인접 정점 next에서 도착 정점 end까지 탐색을 이어간다.

 

visited[next] = false;

재귀호출이 끝난 후에 백트래킹 과정으로 해당 정점의 방문을 취소한다.

 

System.out.println(sb);

8. 함수가 종료되면, sb에 저장된 값을 출력한다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
	static int[] cnt;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(bf.readLine());
		cnt = new int[N+1];
		
		for(int i=0; i<=N; i++) {
			list.add(new ArrayList<Integer>());
		}
		
		for(int i=0; i<N-1; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list.get(a).add(b);
			list.get(b).add(a);
		}
		
		int Q = Integer.parseInt(bf.readLine());
		for(int i=0; i<Q; i++) {
			st = new StringTokenizer(bf.readLine());
			int t = Integer.parseInt(st.nextToken());
			
			int[] tmpCnt = new int[N+1];
			boolean[] visited = new boolean[N+1];
			
			if(t == 1) {
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				visited[start] = true;
				bfs(start, end, 0, visited, tmpCnt);
			}else {
				int num = Integer.parseInt(st.nextToken());
				sb.append(cnt[num]).append("\n");
			}
		}
		System.out.println(sb);
	}
	public static void bfs(int start, int end, int count, boolean[] visited, int[] tmpCnt) {
		if(start == end) {
			for(int i=1; i<=N; i++) {
				if(visited[i]) {
					cnt[i] += tmpCnt[i];
				}
			}
			return;
		}
			
		for(int next: list.get(start)) {
			if(!visited[next]) {
				visited[next] = true;
				tmpCnt[next] += count+1;
				bfs(next, end, count+1, visited, tmpCnt);
				visited[next] = false;
			}
		}
		return;
	}
}

 

https://www.acmicpc.net/problem/23835