유니온파인드

    [Java] 백준 1967 (여행 가자) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1967 (여행 가자) Gold 4

    Problem : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net Approach 유니온 파인드(Union-Find) 를 활용한 문제였다. 플로이드 와샬 알고리즘으로도 풀이가 가능하다고 한다. (여기서는 다루지 않는다.) 주어진 여행 경로가 어떤 형식으로든 서로 연결되어 길이 존재한다면 가능한 여행경로라고 볼 수 있다. 따라서 입력데이터를 받아 도시 사이에 길이 있다면 같은 집합으로 묶는 작업을 진행한다. 그런 뒤에 여행경로에 있는 모든 도시들..

    [Java] 백준 16724 (피리 부는 사나이) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16724 (피리 부는 사나이) Gold 2

    Problem : https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net First Approach 처음 문제를 보고 단순 BFS 인 줄 알았다. 하지만 시작점에 따라 집합의 개수가 달라진다. // ex 2 4 DLDL RLRL // 단순 BFS로 (0,0)부터 시작하면 4를 뱉는다. 정답은 2이다. Approach 집합(사이클)의 개수가 몇 개인지를 찾는 문제이다. Union-Find 알고리즘을 사용하였다. 범위를..

    [Java] 백준 13460 (구슬 탈출 2) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 13460 (구슬 탈출 2) Gold 2

    Problem : https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net Approach 삼성 SW 역량테스트 문제라고 한다. 삼성에서는 이런 구현(시뮬레이션) 문제를 많이 내는 것 같다. BFS 를 사용하여 구현하였다. 이 때 visited 배열이 4차원 배열인 것을 주의하자. visited[blueX][blueY][redX][redY] 의 형태로 구성하였다. 일단 입력 데이터를 처리하면서, 초기 파..

    [Java] 백준 1774 (우주신과의 교감) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1774 (우주신과의 교감) Gold 4

    Problem : https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net Approach MST(Minimum Spanning Tree) 를 응용한 문제이다. 이미 사용된 간선이 존재할 때, 나머지 간선들로 MST를 구성하면 된다. 나는 크루스칼 알고리즘을 사용하였다. 이미 사용된 간선들을 union으로 묶은 뒤, 간선의 길이가 작은 것부터 PQ에서 꺼내 연결하였다. 연결할 때마다 res 변수에 간선의 길이를 저장했고, 모두..

    [Java] 백준 1717 (집합의 표현) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1717 (집합의 표현) Gold 4

    Problem : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net Approach Union-Find(Disjoint Set) 알고리즘을 사용한 기본 문제이다. 유니온파인드를 구현이 다인 문제이다. 입력의 처음이 0 인 경우, union 메소드를 적용하여 하나의 집합으로 묶는다. 입력의 처음이 1 인 경우, 두 숫자의 부모를 검사하여 같은 집합인지를 판단한다. Code import java.io.*; i..

티스토리툴바