본문 바로가기

전체 글

 (45)
[백준 11404 : JAVA] 플로이드 / 플로이드 와샬 개요 문제 이름처럼 플로이드 와샬 알고리즘을 사용한다. 플로이드 와샬은 다익스트라, 벨만포드와 같이 간선의 가중치가 1이 아닌경우에 최단경로를 찾는데 사용된다. 각각의 특징을 짧게 나마 정리하면, 다익스트라 - 한 노드 ▶ 모든 노드 / 빠름 / 가중치가 음수이면 구할 수 없다. 벨만 포드 - 한 노드 ▶ 모든 노드 / 중간 / 가중치가 음수일 때 다익스트라 대신 사용할 수 있다. 플로이드 와샬 - 모든 노드 ▶ 모든 노드 / 느림 / 가중치가 음수여도 사용할 수 있다. 각 알고리즘 문제를 풀어보며 생각되는 가장 간단한 특징들이다. 문제를 보면 모든노드 ▶ 모든 노드로 가는 최단 경로를 구하라는 것을 알 수 있다. 그러므로 플로이드 와샬 알고리즘을 구현하도록 한다. 문제 n(1 ≤ n ≤ 100)개의 도..
[백준 9370 : JAVA] 미확인 도착지 / 다익스트라 개요 다익스트라를 이용해서 풀이할 수 있는 문제이다. 다익스트라가 처음이라면 아래의 문제를 먼저 풀고 오는 것을 추천한다. 아래에 링크에는 다익스트라 알고리즘에 대한 설명이 포함되어 있다. 2020/02/09 - [알고리즘/백준] - [백준 1753 : JAVA] 최단경로 / 다익스트라 [백준 1753 : JAVA] 최단경로 / 다익스트라 개요 이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이할 수 있다. 다익스트라는 음의 가중치를 가지는 경우 사용할 수 없다. 다익스트라를 구현할 때 인접행렬, 인접 리스.. dragon-h.tistory.com 이 문제는 말은 길지만 간단히 정리하면 출발점 -> 도착지 까지의 최단거리 중 특정 간선을 지나는 경우를 구하는 문제이다...
[백준 1504 : JAVA] 특정한 최단 경로 / 다익스트라 개요 다익스트라 알고리즘을 이용하여 약간의 응용(?)을 하면 풀이가 가능하다. 다익스트라가 처음이라면 아래의 문제를 먼저 풀고 오는 것을 추천한다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 www.acmicp..
[백준 1753 : JAVA] 최단경로 / 다익스트라 개요 이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이할 수 있다. 다익스트라는 음의 가중치를 가지는 경우 사용할 수 없다. 다익스트라를 구현할 때 인접 행렬, 인접 리스트 둘 다 구현할 수 있는데 리스트가 효율적인 경우가 많기 때문에 인접 리스트로 구현하였다. 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 풀이 다익스트라는 한 노드에서 모든 노드로 가는 최단거리를 구할 수 있다. 이때 최단거리를 저장하는 배열 + 우선순위 큐를 이용하여 구현할 수 있다. 위의 입력 값을 그래프로 표현하면 다음과 같다. 아래의 표는 최단거리를 저장하는 배열에 값들을 ..
[백준 2206 : JAVA] 벽 부수고 이동하기 / BFS 개요 가중치가 1이고 최단거리를 구하는 문제이다. 그러므로 BFS를 이용하여 풀이 할 수 있다. 어렵게 생각할 거 없이 기존 graph정보를 저장할 배열 -> arr 이동한 거리를 저장할 배열 -> resultArr 벽을 부쉰 횟수를 저장할 배열 -> breakCntArr 위의 3가지 배열을 통해 풀이할 수 있다. 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이..
[백준 1697 : JAVA] 숨바꼭질 / BFS 개요 BFS는 최단거리를 구하는 경우 가중치가 1일 때 사용할 수 있다. 이 문제는 동생과 형의 시작 지점이 같을 경우 반례 때문에 삽질 좀 했다. 자신 스스로 반례를 찾는 습관을 가지는 것을 추천한다! 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 풀이 1. 형의..
[백준 7569 : JAVA] 토마토 / BFS 개요 이 문제는 아래의 문제에서 배열만 3차원 배열로 변경된 문제이다. 아래 문제를 풀고 이 문제를 접근하면 쉽게 풀이할 수 있을 것이다. 2020/02/09 - [알고리즘/백준] - [백준 7576 : JAVA] 토마토 / BFS [백준 7576 : JAVA] 토마토 / BFS 개요 BFS와 DFS는 탐색 알고리즘이다. 둘 중 어떤 알고리즘을 선택할 것인지 선택해야 할 때 나는 보통 둘이 탐색하는 모양을 생각해본다. DFS는 한 노드에 도달 했을 때 갈 수 있는 노드가 있는 경우 끝까지 찾고.. dragon-h.tistory.com 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서..
[백준 7576 : JAVA] 토마토 / BFS 개요 BFS와 DFS는 탐색 알고리즘이다. 둘 중 어떤 알고리즘을 선택할 것인지 선택해야 할 때 나는 보통 둘이 탐색하는 모양을 생각해본다. DFS는 한 노드에 도달 했을 때 갈 수 있는 노드가 있는 경우 끝까지 찾고 돌아오고, BFS는 물의 파장처럼 점진적으로 퍼지며 탐색을 진행한다. 따라서 이문제는 익은 토마토 중심으로 점진적으로 퍼저나가며 토마토를 익게 만들기 때문에 BFS를 선택한다. 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익..

티스토리툴바