School algo07 그래프탐색

다익스트라 백준 관련문제: 1753

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
 * @Info 문제 A: 무방향 그래프의 연결 여부
 *
 * 양쪽 정점을 의미하는 List 2개 모두에 상대방 정점 추가하기
 */

public class Practice3 {
    public static int bfs(List<List<Integer>> graph, int start, boolean[] visited) {
        Queue<Integer> que = new LinkedList<>();
        visited[start] = true;
        que.add(start);
        int count=0;
        while(!que.isEmpty()) {
            int v = que.poll();
            count++;
            for(var nextV:graph.get(v)){
                if(!visited[nextV]){
                    que.add(nextV);
                    visited[nextV]=true;
                }
            }
        }
        return count;
    }

    public static List<Integer> solve(List<List<Integer>> graph) {
        int length = graph.size();
        boolean[] visited = new boolean[length];
        int maxsize = 0;
        int answer = 0;
        List<Integer>components=new ArrayList<>();
        for (int i = 0; i < length; i++) {
            if(!visited[i])
                components.add(bfs(graph, i, visited));
        }
        return components;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            if (E == 0)
                System.out.printf("%d 1%n", N);
            else {
                List<List<Integer>> graph = new ArrayList<>();
                for (int i = 0; i < N; i++)
                    graph.add(new ArrayList<>());
                int[] data = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                int j = 0;
                for (int i = 0; i < E; i++) {
                    int from = data[j++];
                    int to = data[j++];
                    graph.get(from).add(to);
                    graph.get(to).add(from);
                }
                List<Integer>components=solve(graph);
                System.out.printf("%d %d\n", components.size(), Collections.max(components));
            }
        }
    }
}

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
/**
 * 
 * @Info 문제B: DFS를 이용한 방향 그래프에서 주기 찾기
 * 
 * 방향 그래프이지만 인접리스트 이용함
 */
public class Main {

	
    public static boolean detectCycle(boolean[] visited, 
        List<List<Integer>> G, int v, Set<Integer> visiting) {
        visiting.add(v);
        for(var w: G.get(v)) {
            if(visited[w]) continue;
            if(visiting.contains(w)) return true;
            if(detectCycle(visited, G, w, visiting)) return true;
        }
        visited[v] =  true;
        return false;
    }
  
    public static boolean solve(List<List<Integer>> G) {
        boolean[] visited = new boolean[G.size()];
        Set<Integer> visiting = new HashSet<Integer>((int)(visited.length*1.3));
        for(int i = 0; i < visited.length; ++i) {
            visiting.clear();
            if(visited[i]) continue;
            // if(G.get(i).isEmpty()) visited[i] = true;
            else if(detectCycle(visited, G, i, visiting)) 
                return true;
        }
        return false;
    }
       
    public static void main(String[] args) {
        try(
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in))
        ){
            int T = Integer.parseInt(in.readLine());
            for(int t = 0; t < T; ++t) {
                StringTokenizer st = new StringTokenizer(in.readLine());
                int N = Integer.parseInt(st.nextToken());
                int M = Integer.parseInt(st.nextToken());
                if(M == 0){
                    in.readLine();
                    System.out.println(false);
                }
                else{
                    List<List<Integer>> G = new ArrayList<>(N);
                    for(int i = 0; i < N; ++i) G.add(new LinkedList<Integer>());
                    int[] edgeInfo = Arrays.stream(in.readLine().split(" "))
                        .mapToInt(Integer::parseInt).toArray();
                    for(int i = 0; i < M*2; i += 2) 
                        G.get(edgeInfo[i]).add(edgeInfo[i + 1]);
                    System.out.println(solve(G));
                }
            }
        }
        catch(Exception e) {
            e.printStackTrace();
        }
    }
}

 

문제 C: 가중치 방향 그래프에서 최단 경로 길이 구하기

Lazy Dijkstra를 이용한 풀이

 

힙은 항상 최소값을 반환한다. 따라서 힙에서 튀어나왔는데 방문이 된 것이라면 그것은 이미 과거에 더 작은 값으로 갱신되어 정답으로 선정된 이미 방문된 노드이다. 

 

왜 교과서의 dijkstra와는 다르게 우선순위 큐를 이용한 Lazy Dijkstra에서는 distance배열을    distance=[INF]*numV

와 같이 INF로 초기화시켜야만 하나(교과서가 잘못되었다.교과서도 distance배열을 INF로 초기화 시켜주어야 한다)?

 

dist는 처음에 무한대로 놓아야 한다. 왜냐하면 초기화되는 dist배열의 의미는 내가 진짜 구하고자 하는dist의 의미(내가 설정한 시작점에서 해당정점까지의 거리인 dist[ver]+graph[ver][nextV])와 다르기 때문이다. 기본적으로 내가 구하고자 하는 dist의 값이 dist=list(graph[startV])로 설정된 값보다 크다. 그런데 dist를 정말 dist=list(graph[startV])와 같이 설정한다면 if문을 통과하여 dist를 갱신할 수 없게 된다(if(not visited[nextV] and graph[ver][nextV]!=INF and distance[nextV]>distance[ver]+graph[ver][nextV]):).

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;
 
public class Main {
public static final int INF=987564321;
    public static class Node{
        private int node;
        private int weight;
        public Node(int node, int weight){
            this.node=node;
            this.weight=weight;
        }
        public int getWeight(){
            return weight;
        }
    }
    public static int[] solve(List<List<Node>>graph, int start, int[]des){
        int[] answer=new int[des.length];
        int []result=dijkstra(graph, start);
        for(int i=0;i<des.length;i++){
            if(result[des[i]]==INF)
                answer[i]=-1;
            else
                answer[i]=result[des[i]];
        }
        return answer;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int[] graphInfo = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int V = graphInfo[0];
            int E = graphInfo[1];
            int S = graphInfo[2];
            int N = graphInfo[3];
            int[] dest = new int[N];
            System.arraycopy(graphInfo, 4, dest, 0, N);
            List<List<Node>> graph = new ArrayList<>(V);
            for (int i = 0; i < V; i++)
                graph.add(new ArrayList<Node>());
            int[] edgeInfo = null;
            if (E == 0) br.readLine();
            else edgeInfo = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
 
            int j = 0;
            for (int i = 0; i < E; i++) {
                int from = edgeInfo[j++];
                int to = edgeInfo[j++];
                int weight = edgeInfo[j++];
 
                graph.get(from).add(new Node(to, weight));
            }
            int[] ret = solve(graph, S, dest);
            System.out.println(Arrays.stream(ret).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
        }
    }
    public static int[] dijkstra(List<List<Node>> graph, int start){
        PriorityQueue<Node>que=new PriorityQueue<>(Comparator.comparingInt(Node::getWeight));
        int size=graph.size();
        boolean[]visited=new boolean[size];
        int[]distance=new int[size];
        Arrays.fill(distance,INF);
        distance[start]=0;
        que.add(new Node(start, 0));
        for(int i=0;i<size;i++){
            while(!que.isEmpty()){
                Node cur=que.poll();
                if(visited[cur.node])continue;
                visited[cur.node]=true;
                for(var nextN:graph.get(cur.node)){
                    if(!visited[nextN.node] && distance[cur.node]+nextN.getWeight()<distance[nextN.node]){
                        distance[nextN.node]=distance[cur.node]+nextN.getWeight();
                        que.add(new Node(nextN.node, distance[nextN.node]));
                    }
                }
            break;
            }
        }
        return distance;
    }
 
 
}

 

 

문제 D: 최소 경로 합

출처: https://leetcode.com/problems/minimum-path-sum/

착안점:

1. BFS의 핵심은 주변노드를 한번씩 훓어본다는 것이다.물론 기존에 방문한 노드라면 주변노드라도 그냥 넘긴다. 하지만 핵심은 한번씩 훓어 본다는 것이고 만약 기존에 방문했던 노드라도 조건을 바꾸어 주면 훓어볼수 있다는 것이다. 그냥 매번 똑같이 내가 알던 BFS를 쓰는 것이 아니다. 응용해 가는 것이다.

2. 화살표 방향이 오른쪽과 아래만 있어서 BFS를 쓸수 있는것이다? 아니다. 화살표가 위,아래, 왼쪽, 오른쪽 모두 갈수 있어도 BFS를 사용할 수 있다. 왜? BFS는 인근노드라면 기본적으로 모두 접근 가능하므로. 

 

나도 어떻게든 시잔복잡도 줄이려고 부단히 노력했다. 그러나 교수의 코드만큼 시간을 앞당기지는 못했다!!! 그러나! 이렇게 말하기 좀 그렇지만 부질없게 느껴진다. 물론 시간 적게 걸릴수록 좋지... 근데 그거 좀 줄일려고 이런 감정소모, 에너지 소모... 투자시간대비 이정도 시간복잡도 줄이자고 그많은 감정소모를 해? 그냥 빨리 실패하고 빨리 질문 때리는게 상책이다!! 

결과를 말하자면 내 최종코드에서는 다른 이전의 keeping에 있던 값들과 비교하여 없으면 큐에 또 새로운 요소를 넣는 것이고 교수의 코드는 오로지 visited가 -1이 아닌 경우나 기존에 visited[r]r[c]에 들어가 있는 값보다 새로 만들어진 값(temp)이 작은 경우에만 큐에 새로운 요소를 넣는다. 

두 코드의 공통점은 모두 어떻게든 적게 넣을려고 한것이고 차이점은 교수의 코드가 큐에 더 적게 넣음으로써 시간복잡도와 공간복잡도를 동시에 줄일 수 있다는 것이다. 

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;


class Solution{
    public static class Position{


        private int r;
        private int c;

        public Position(int r, int c) {
            this.r = r;
            this.c = c;
        }

        public int getR() {
            return r;
        }
        public int getC() {
            return c;
        }
    }
    public int minPathSum(int[][] grid) {
        int row=grid.length;
        int column=grid[0].length;
        int r=row-1;
        int c=column-1;
        int[][]visited=new int[row][column];
        for(int i=0;i<row;i++)
            Arrays.fill(visited[i], -1);
        visited[0][0]=grid[0][0];
        Queue<Position>que=new LinkedList<>();
        que.add(new Position(0,0));
        while(!que.isEmpty()){
            Position cur=que.poll();
            if(cur.r==r && cur.c==c)return visited[r][c];
            if(cur.r<r){
                int candiR=visited[cur.r][cur.c]+grid[cur.r+1][cur.c];
                if(visited[cur.r+1][cur.c]==-1 || candiR<visited[cur.r+1][cur.c]) {
                    que.add(new Position(cur.r+1,cur.c));
                    visited[cur.r + 1][cur.c] = candiR;
                }
            }
            if(cur.c<c){
                int candiC=visited[cur.r][cur.c]+grid[cur.r][cur.c+1];
                if(visited[cur.r][cur.c+1]==-1 || candiC<visited[cur.r][cur.c+1]) {
                    que.add(new Position(cur.r, cur.c+1));
                    visited[cur.r][cur.c + 1] = candiC;
                    
                }
            }
        }
        return visited[r][c];
    }

}