백준) BFS, 다익스트라

숨바꼭질 1679번

---

내가 떠올린 풀이 해설

BFS를 응용해서 푸는 문제였다. BFS()를 호출한 후 BFS에서 arr 배열을 최대 크기 배열로 생성한 후 Queue에 n을 add한다. Queue가 비어있을 때까지 반복한다. now 값에 Queue에서 poll 한 값을 대입하고 for문을 i가 3보다 작을 때까지 반복한다. 1초 후에 now - 1, now + 1, now * 2로 움직여야한다. 만약 next가 k와 같다면 arr[now]를 리턴해준다. 또한 만약 next가 0보다 크거나 같고 next가 100001보다 작아야하고 arr[next]가 0일 때 arr[next]에 arr[now] + 1을 대입한다. 그리고 Queue에 next를 add한다.

---

정확한 풀이

import java.util.*;
public class Baek1697 {
	static int n;
	static int k;
	static int[] arr;
	static Queue<Integer> que = new LinkedList<>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		
		if (n >= k) {
            System.out.println(n - k);
        } else {
            System.out.println(BFS());
        }
	}
	private static int BFS() {
		arr = new int[100001];
		que.add(n);
		arr[n] = 1;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int i = 0; i < 3; i++) {
				int next;
				if (i == 0) {
                    next = now - 1;
                } 
				else if (i == 1) {
                    next = now + 1;
                } 
                else {
                    next = now * 2;
                }
                if (next == k) {
                    return arr[now];
                }
                if (next >= 0 && next < 100001 && arr[next] == 0) {
                    arr[next] = arr[now] + 1;
                    que.add(next);
                }
			}
		}
		return 0;
	}
}

---

파티 1238번

---

내가 떠올린 풀이 해설

이 문제를 푸는데 시간이 오래 걸렸다. 다익스트라에서 조금만 응용하면 되는 문제였다. 1~N을 출발점으로 파티 마을 X까지의 거리를 다익스트라로 구한다. 그리고 반대로 파티 마을 X를 출발점으로 다익스트라를 돌려서 각 마을까지의 거리를 구했다. 그리고 이 두 값을 마을마다 더해주면 오고 가는 거리가 나오는데 이 값들 중 최댓값을 구하면 된다. time 배열은 파티 마을까지 오고 가는 거리의 값이다. 1~N 마을을 출발지로 다익스트라를 돌린 후 X까지의 거리를 time에 더해준다. 그 후 X를 출발지로 각 마을까지 거리를 구하여 time에 더해준다. 그 이후 time의 값들 중 최대값을 출력한다. 그 다음 dijkstra를 호출하고 다익스트라 메서드에서 우선순위 큐에 시작 정점을 넣어준다. 시작 지점의 가중치는 0이다. visit, distance를 초기화하고 distance에는 -1을 넣어준다. 우선순위 큐가 빌 때까지 while문을 반복한다. 현재 정점에 방문하지 않았을 때 연결된 정점들에 대해 검사를 시작한다. 연결된 정점의 가중치가 -1이거나 연결된 정점의 가중치가 현재 정점의 가중치와 현재 간선의 가중치의 합보다 클 때 값을 업데이트한다. 업데이트 후 다음 정점을 우선순위 큐에 넣어준다. Circle 클래스는 정점의 번호와 가중치를 가진다. 우선순위 큐의 타입으로 이용하기 위해 Comparable을 implements 해준다. 정렬 기준은 가중치의 오름차순이다.

---

 

참고 블로그

https://jellyinghead.tistory.com/79

[백준 1238] 파티 (자바)

---

정확한 풀이

import java.util.*;
import java.io.*;

public class Baek1238 {
	static int[] distance;
	static boolean[] visit;
	static ArrayList<Circle>[] list;
	static PriorityQueue<Circle> que = new PriorityQueue<>();
	
	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());
		int m = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		visit = new boolean[n + 1];
		list = new ArrayList[n + 1];
		distance = new int[n + 1];
		
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<Circle>();
		}
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			list[u].add(new Circle(v, w));
		}
		int time[] = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dijkstra(i);
            time[i] += distance[x];
        }
        
        dijkstra(x);
        for(int i = 1; i <= n; i++)
            time[i] += distance[i];
        
        int max = 0;
        for(int i = 1; i <= n; i++) 
            max = Math.max(max, time[i]);
    
        System.out.println(max);
	}

	private static void dijkstra(int x) {
		que.offer(new Circle(x, 0));
		visit = new boolean[visit.length];
		distance = new int[distance.length];
        Arrays.fill(distance, -1);
		distance[x] = 0;
		while(!que.isEmpty()) {
			Circle current = que.poll();
			int c_v = current.vertex;
			if(visit[c_v]) {
				continue;
			}
			visit[c_v] = true;
			for(int i = 0; i < list[c_v].size(); i++) {
				Circle tmp = list[c_v].get(i);
				int next = tmp.vertex;
				int value = tmp.value;
				if(distance[next] == -1 || distance[next] > distance[c_v] + value) {
					distance[next] = distance[c_v] + value;
					que.add(new Circle(next, distance[next]));
				}
			}
		}	
	}
}	
class Circle implements Comparable<Circle> {
	int vertex, value;
	Circle(int vertex, int value) {
		this.vertex = vertex;
		this.value = value;
	}
	@Override
	public int compareTo(Circle o) {
		return value - o.value;
	}
}

---

오늘의 회고

오늘은 BFS와 다익스트라 문제를 풀었습니다. 두 문제 모두 조금만 응용해서 푸는 문제였고, 너무 오랫만에 BFS와 다익스트라 문제를 풀어서 시간이 오래걸렸습니다. 다른 개념들도 까먹지않게 여러 개념의 문제들을 풀어야할 것 같습니다. 조금만 화이팅하자