hyeoneee's blog

두번째로 벨만포드를 정리해보고자 한다.

음수 가중치가 있을때 최단거리를 구하는 알고리즘이다.

V번 E개의 간선에 대해 dist 배열 갱신한다.
* V번째에 dist 배열의 갱신이 발생하면 -> 음의 사이클 존재

요 음의 사이클이 존재 하는지 안하는지가 벨만포드에서 가장 중요하다.

이유는? (V-1)번까지 돌았는데 V번째에서 dist 배열 갱신이 발생한다면?

사이클이 있는데 그값이 계속 감소한다는 것이다. 가중치가 음수가 있기 때문에 가능한 현상이다.

그래서 문제를 풀다보면 음의 사이클이 있는가? 를 묻는 문제도 더러 있다

샘플코드 

    static int[] dist;
    static int N;
    static ArrayList<Node>[] adj = new ArrayList[N+1];
    static int belman() {
        //1. dist 배열 INF 값으로 채우기, 출발지는 0으로
        Arrays.fill(dist, INF);
        dist[1] = 0;

        //2. V번 E개의 간선은 탐색 (음수 사이클 체크를 위해 V-1+1번 체크)
        boolean isUpdated;
        for (int i = 1; i <= N; i++) { // V
            isUpdated = false;
            for (int here = 1; i <= N; here++) {// E
                for (Node next : adj[here]) {//dist 배열 업데이트
                    int nextCost = dist[here] + next.cost;
                    if (dist[here] != INF && dist[next.idx] > nextCost) {
                        //dist[here] != INF : 연결이 안된다는 것을 확인 , 현재노드인 here가 이전에 방문했어야함 그래야 거쳐서 가니깐 
                        dist[next.idx] = nextCost;
                        isUpdated = true;
                    }
                }
                if (!isUpdated) break; // 더 이상 최단 경로 갱신이 안일어 나면 조기종료
            }
            if (isUpdated) return -1;
        }
        return dist[N];
    }

어떤 정점에서 출발해서 모든 노드들로 가기까지 최단거리들을 구하는 알고리즘

특징

1. 음의 가중치가 없다. 무조건 양의 가중치이다.

-> 가중치가 모두 같으면? BFS로푼다.

2. 이전에 풀었던 부분 최단거리가 최단거리임을 보장한다.

3. Priority Queue를 사용하여 가중치순으로 정렬한다.

Priority Queue<Node> pq = new Priority Queue <>( (o1,o2)->Long.compare(o1.cost,o2.cost);

pq를 사용하는 이유?

• Cost순으로 정렬되기 위해, 거리가 적은 순으로 뽑아서 그 노드를 거쳐서 가면
• 최소임이 보장되기 때문에 pq를 사용한다.

4. 최단거리 배열은 MAX값으로 초기화 시켜준다 ( 최단거리를 구하기 위해)

5. 인접배열은 양방향, 단방향을 고려해준다.

응용

1. 왔다 갔다 최단거리 (출발 -> 도착 정점 -> 출발)

-  출발정점에서 최단거리 구하고 도착정점에서 최단거리 더해서 두개 더해

2. 단일 도착 지점에 대한 최단거리 (1~N-1 번 정점에서 출발 N번 도착)

- 반대로 N에서 출발해서 최단거리 구하기

3. 여러 지점에서 출발하는 최단거리

- 가상의 출발지점에서 가중치 0으로 출발 지점들을 연결한 후 최단거리 구하기

4. 최단거리의 경우의 수 구하기 ( 백준 14554 )

 - 배열하나를 더 선언해, 최단거리로 업데이트 하면, 다음 경로로 가는 경우의 수에 기존 경로의 수를 넣어주고,

   최단거리가 같으면? 해당 지점에 오는 경우의수가 늘어나는 것이므로, 

   다음 경로의 수에 기존경로+ 다음경로를 더해준다.

                        if (dist[newX][newY] > dist[now.x][now.y] + cost) { // 최단거리 업데이트
                            dist[newX][newY] = dist[now.x][now.y] + cost;
                            pq.add(new Node(newX, newY, dist[newX][newY], 0));
                            path[newX][newY] = path[now.x][now.y];
                        } else if (dist[newX][newY] == dist[now.x][now.y] + cost) { // 최단거리가 같으면
                            path[newX][newY] = path[now.x][now.y] + path[newX][newY]; // 경우의수 누적
                        }

샘플 코드

    static int[] dist;
    static int N;
    static PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Long.compare(o1.cost,o2.cost));
    static ArrayList<Node>[] adj = new ArrayList[N+1]; // main에서 초기화 필요 
	static void dijkstra() {
        //0. 초기화 dist 배열 INF 값으로 채우기 , 시작점은 0, q에 시작점 add
        Arrays.fill(dist, INF);
        dist[1] = 0;
        pq.add(new Node2(1, 0));

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (dist[now.idx] < now.cost) { // 현재 노드의 최소거리가 가져온 cost 보다 작다면 넘어가도됨
                continue; // 이미 최단거리를 확정했으면 돌필요가없음 아니면 시간초과
            }
            for (Node next : adj[now.idx]) {
                if (dist[next.idx] > dist[now.idx] + next.cost) { // 최단거리이면
                    dist[next.idx] = dist[now.idx] + next.cost; // 거리 업데이트 해주고
                    pq.add(new Node(next.idx, dist[next.idx]); // pq에 값 넣기 -> cost : 업데이트된 거리값
                }
            }
        }
    }

알고리즘 시험에 패스한 기념으로

그동안 알고리즘 공부한걸 정리해보고자 한다 ^^ (기쁜맘으로)

그렇담 우선 Graph 최단거리 3종 아이들부터 정리해보고자 한다.

최단거리 알고리즘은 3가지가 대표적이다.

1. 다익스트라

2. 벨만포드

3. 플로이드 워셜

1) 시작점 , 도착점

1 to 1 : 다익스트라

1 to N : 다익스트라

N to 1 : 다익스트라 (역방향 그래프를 만들어 도착점을 출발점으로 하는 1 to N 다읷트라 수행) - 역다익

N to N : 플로이드 워셜

2) 간선의 가중치

가중치가 없으면?   BFS

가중치가 있으면서 양수이면 ? 다익스트라 (=> Priority Queue 사용)

가중치가 있으면서, 음수이면? 벨만포드 

3) 트리 

-> LCA

BFS를 연습해보기 위해서 

이 문제를 풀어보았다.

main에서는 먼저 데이터를 map에 넣어주고

가장 중요한 것은 

해당단지마다 bfs를 돌려준다는 것이다...

한번에 bfs를 돌려서 전체 탐색을 하는 것이 아니라

단지마다 bfs를 돌려서

해당 단지에 집이 몇가구 있는지를

세어야 하기 때문이다.

그리고 몇단지인지도 세어야 하기때문에 

사실 bfs를 처음 호출되는 횟수만큼이

단지 수라고 볼 수 있겠다.

queue에 데이터를 관리하기 쉽게 pos에

정점 y와x를 선언해서

class를 선언해주었다.

그리고 가장 중요한

bfs method

먼저 queue에 값을 넣어주고

queue가 빌때까지

while문을 돌려준다.

그리고 d 배열 

그니깐 아래,위,오른쪽,왼쪽으로 

이동할 좌표를 입력해놓은 배열을

for를 돌면서

새로운 좌표를 구해준다

그게 newY, newX

구한 새로운 좌표값을 먼저

1. 경계값을 체크해준다.

( 0보다 큰지, N 보다 작은지)

2. 그리고 단지에 포함되는지를 체크한다

map[newY][newX] == 1

3. 그리고 방문한 적이 있는지? 도 체크해준다

visited[newY][newX] == fasle

해당 조건들이 모두 통과가 되었으면

queue에 들어갈 자격이 된닷!!

그렇다면 

queue에 값을 넣어주고 

방문했다고 체크해주고

그리고 단지내 가구수의 count 를 늘려준닷

그리고 해당 queue가 비면

(단지내 가구를 모두 방문했으면)

해당 단지내 가구수 가 나왔기 때문에

정답인 ArrayList에 count 배열을 넣어준다.

그리고 맨마지막에 출력할때에는

ArrayList의 수가 총 단지의 수이고

각 count가 단지내 가구 수가 된다.

그래서 ArrayList를 라이브러리를 

이용해 정렬해주고

출력해주면된다~~

트리를 이해하는 문제이다

이문제는 완전 이진트리를 중위 순회 하는 방법이다

중위 순회는 루트 노드를 중간에 읽는 방법이다

LEFT자식 -> ROOT -> RIGHT 자식

참고로

전위 순회 : ROOT -> LEFT -> RIGHT

후위 순회 : LEFT -> RIGHT ->ROOT

해당 문제에서 input이 이런식으로 들어오므로 input을 받을 때 주의 해야한다.

하지만 완전이진트리에서는 이걸 감안할 필요가 없다 트리에 들어가는 순서가 일정하기 때문이다.

그러므로 index와 value값만 받고 나머지는 무시해준다 ^_^;;

그래서 해당 tree 테이블에 해당 index값에 value값을 넣어주고

그다음 중위 순회 하는 function을 call 해준다.

먼저 해당 function을 나가는 조건을 명시해준다.

1. node가 tree의 수를 벗어나거나

2. tree에 값이 없다

그리고 참고로

tree는 인덱스가 0이 아닌 1부터 시작하도록 설계해주었다

완전이진 트리이므로

그리고 숫자 계산하기도 이게더 편하다.

그리고 먼저 LEFT를 먼저 뽑아줄거니깐

*2를해서 inOrder 메소드를 호출하고

그다음 출력 (ROOT)

그다음 오른쪽 자식 호출 *2+1

전위, 후위 순위는 이 출력하는 라인만 순서만 바꾸어 주면된다

다음은 input , output 파일이다.

이문제는 사실 이해만 하면 그닥 어렵지않다

처음에 풀었던 코드에서

좀더 성능좋게 해서 고쳐봤다

다음 문제를 풀어보겠다

무척 쉬운문제다 ;; 

findAns 함수가 핵심인데

우선 나는 한 중앙 아이를 잡고

거기서 앞뒤 1칸, 두칸의 아이들을 비교하였다

그런데, 조망권이 확보되려면 중앙 아이가 

양쪽의 아이들보다 커야 하므로,

그걸 먼저 검사해주었다 그 function이 isBig이고

그래서 검사하는 아이가 양쪽보다 크면 그제서야 조망권이 몇인지 체크한다.

조망권은 네개값 비교한것중 가장 작은 값으로 설정하면된다.

왜냐하면 하나라도 걸리면 조망권이 확보가 안되므로

그래서 Math.min값으로 구해주었다.

그런데 이 값은 항상 isBig이 네번 호출되므로 그닥 좋은 성능은 아닌거 같다

ㅋ_ㅋ;;

이 문제는 Union & Find 문제이다.

공통 원소가 없는, 즉 상호 배타적인 부분 집합들로 나눠진
원소들에 대한 정보를 저장하고 조작하는 자료구조

초기화에는 자신이 부모인 것으로 초기화 해준다.

그리고 나서 부모 - 자식 관계

즉, 문제에서 동맹관계를 알려주면

해당 부모 자식관계를 par[] 배열에 맺어준다

 그런데 어차피

동맹의 동맹은 동맹이므로

최종적으로 가장 높은 root를 같은걸 가리키고 있으면

같은 동맹이란 사실을 알 수 있다.

그래서 find 펑션에서

가장 높은 root를 찾을 수있도록 재귀로 구현해주었다.

동맹관계를 맺어주는

type =0 이면

각각 부모 - 자식관계를 맺어주고

type =1 이면 가장 높은 root를 구해주는

find 펑션을 통해

그 값이 같은지 비교해서

출력해준다.

DFS와 BFS 문제이당

츄욱,,,,,

대학교때 다 했던건데,,,

지나면 까먹는닷 ^^,,,

그래도 교수님이 잘 설명해주셔서

엄청!! 잘이해했다

(지금만큼은,,,)

여기선 하나만 더하면된다

기본적인 DFS와 BFS를 하고

오름차순 순으로 출력하라고 했으니깐

인접리스트에 오름차순으로 넣어주면 된당!!!!

츄욱,,,

이거때문에 선생님한테 물어도 봣당^_^,,,,,

BFS는

큐를 사용하였고

DFS는 스택을 사용하였당

그리고 DFS는 재귀를 사용!

그리고 C배열을 이용하여

방문하였는지 안하였는지를 쳌쳌!!!!