BOJ

    [java] 백준 1707 (이분 그래프) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 1707 (이분 그래프) Gold 4

    Problem : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net Approach 풀이에 시작하기 앞서 주의할 점을 소개한다. 이 문제는 은근히 반례를 찾는 유저들이 많았는데 대부분 다음과 같은 이유로 오답이 생겼을 것이다. 질문 게시판에 있는 djm03178님의 게시글을 인용하겠다. 테스트 케이스마다 초기화를 해야 한다. 똑같은 입력을 주었을 때 다른 출력을 내놓는다면 초기화가 되지 않은 상태일 것이다. 1번 정점에서만 탐색을 하..

    [java] 백준 1956 (운동) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 1956 (운동) Gold 4

    Problem : https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net Approach 최단경로 사이클을 찾는 문제이다. 따라서 플로이드 와샬(Floyd Warshall) 알고리즘을 사용하여야 한다. 참고로 1:N 최단경로 문제는 다익스트라 알고리즘을, 음수사이클을 찾을 때엔 벨만-포드 알고리즘을, N:N 최단경로 문제는 플로이드 와샬 알고리즘으로 접근하면 용이하다. 이 문제에서는 각 노드 A에 대하여 A에서 시작하..

    [java] 백준 10217 (KCM Travel) Gold 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 10217 (KCM Travel) Gold 1

    Problem : https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net Approach 이 문제는 다익스트라 알고리즘과 DP를 같이 사용해서 풀어야했다. 인접리스트를 이용하여 그래프를 구성하였으며, 시간순 오름차순(시간이 같으면 비용순 오름차순)으로 구성하였다. 그런 후, 시작점 1부터 다익스트라 알고리즘을(BFS: PriorityQueue 이용) 적용하여, 비용을 초과하지 않는 선에서 모두 갱신해주었다. 다익스..

    [java] 백준 11404 (플로이드) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 11404 (플로이드) Gold 4

    Problem : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Approach 1 대 N 최단 경로를 구할 때에는 다익스트라(Dijkstra) 알고리즘을 사용하면 된다. N 대 N 최단 경로를 구할 때에는 플로이드 와샬(Floyd Warshall) 알고리즘을 사용하면 된다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택하며 최단경로를 구성해 나갔다면, 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 다음과 같은 ..

    [java] 백준 11657 (타임머신) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 11657 (타임머신) Gold 4

    Problem : https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net Approach 도시 to 도시 의 최단경로비용을 구하는 문제인데, 음수 사이클이 존재할 수도 있는 문제이다. 음수사이클이 존재할 수 있으므로, 다익스트라 알고리즘은 사용이 불가능하다. 문제에서 의도한 바는 벨만-포드(Bellman-Ford) 알고리즘이므로 필자도 그 방법을 이용했다. 벨만-포드 알고리즘은 최단거리로 목..

    [java] 백준 9370 (미확인 도착지) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 9370 (미확인 도착지) Gold 2

    Problem : https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net Approach 다익스트라 알고리즘을 이용하여 푸는 문제이다. 처음 문제를 이해할 때 g나 h로부터 갈 수 있는 노드들을 구하는 문제라고 이해를 했었다. 문제에서 요구한 것을 간단히 쉽게 말하면, 시작점 s에서 임의의 노드 X로 최단거리로 가는 길에 무조건 g-h 혹은 h-g가 있는 노드들을 구하는 것이다. 예를 들어, s = 1, g = 3, h =4 라고 할 때, 1에서..

    [java] 백준 1504 (특정한 최단 경로) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 1504 (특정한 최단 경로) Gold 4

    Problem : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net Approach 가중치가 음수가 아니므로 다익스트라 알고리즘을 이용하여 문제 풀이가 가능하다. 하지만 특정 루트를 반드시 지나가면서 최단거리를 구해야한다. A 부터 B까지 가는 최단경로를 구해야 할 때, V1-V2 경로를 무조건 지나야 한다면, A - V1 - V2 - B A - V2 - V1 - B 위의 두 경로가 존재한다. 따라서 ..

    [java] 백준 1753 (최단경로) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 1753 (최단경로) Gold 5

    Problem : https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net Approach 최단거리를 구하는 문제이다. 1. 단방향 그래프 2. 가중치는 항상 자연수 위의 조건으로 인해 다익스트라(O(Elog(V))를 이용하여 문제 풀이가 가능하다. 다익스트라 알고리즘은 현재 연결된 노드에서 이어진 모든 곳을 일단 방문하여 거리를 계산하여 저장한 후, 새로운 노드와 새로운 간선들이 추가되면, 도달할수 있는 ..

    [java] 백준 2206 (벽 부수고 이동하기) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 2206 (벽 부수고 이동하기) Gold 4

    Problem : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net Approach 조건이 달려있는 경로 최소비용 문제이다. 필자는 BFS를 사용했다. 경우의 수를 따지기 전에, 현재 위치에서 벽을 부시고 왔는지에 대한 brokenWall[x][y] 배열이 필요하다. brokenWall[x][y] 의 값이 2이면, 해당 (x, y)를 아직 방문하지 않았다는 뜻이고, 1이라면, 해당 (x, y)를 방문했는데 방문하기전에 경..

    [java] 백준 7569 (토마토2) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 7569 (토마토2) Silver 1

    Problem : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net Approach 백준 7576번 토마토 문제와 같은 문제이지만, 3차원 배열로 구성된 문제이다. 7576번 문제의 풀이는 밑의 링크에 있다. 2020/12/30 - [Algorithm/Baekjoon Online Judge] - [java] 백준 7576 (토마토1) Silver 1 [java] 백준 7576 (토마토1) Silver 1 Problem : ..

티스토리툴바