DFS
BOJ 1939 중량제한 [Java]
BOJ 1939 중량제한 1. 문제 링크 https://www.acmicpc.net/problem/1939 2. 문제 해설 처음에는 실수로 시간복잡도를 생각 안하고 접근했다. 공장이 있는 섬 두 개 중 한 지점에서 다른 지점까지 갈 수 있는 모든 경로를 살펴보면서 각 경로마다의 최소의 중량제한을 구하고, 그 값의 최대값을 구하는 방식을 dfs로 구현하였다. 시간복잡도가 O(NM)으로 당연히 시간초과가 나왔다. 시간복잡도를 줄일 수 있는 방법이 무엇이 있을까 고민하다가, 각 다리의 중량제한의 범위가 1 ≤ C ≤ 1,000,000,000 으로 굉장히 큰 것을 보고 이분탐색을 떠올렸다. BFS와 이분탐색을 이용해서 풀 수 있는데, 각 로직의 흐름을 설명해보겠다. 이분탐색 로직 이분탐색을 할 대상은 물품의 중..
프로그래머스 Lv.2 게임 맵 최단거리 [Java]
1. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/1844 2. 문제 해설 최단거리를 찾는 대표적인 문제이다. 이렇게 최단거리를 찾아야하는 문제는 bfs를 이용하여서 푸는 것이 편하다. 처음에 풀었을 때는 dfs도 간만에 구현해볼 겸하고 dfs로 풀었다가 시간 초과로 효율성 테스트를 통과하지 못했다. bfs는 목적지에 도착했을 때, 최단거리로 방문하는 것이 보장되지만 dfs는 모든 경우의 수를 다 보기 때문에 더 오랜 시간이 걸리기 때문이다. 3. 코드 보기 import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; class Solution { class..
BOJ 1260 DFS와 BFS [Java]
BOJ 1260 DFS와 BFS 1. 문제 링크 https://www.acmicpc.net/problem/1260 2. 문제 해설 그래프에서의 dfs와 bfs를 할 수 있는지를 묻는 문제이다. 인접 리스트를 이용하여 그래프를 표현해주고 dfs와 bfs를 돌려주면 된다. 주의할 점 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 점이다. : 인접 리스트에서 각 정점의 원소들을 오름차순으로 정렬해주면 쉽게 해결할 수 있다. 2. dfs를 비재귀적인 방식으로 풀 경우 재귀적인 dfs와 방문 순서가 다를 수 있다. : 나는 dfs를 재귀적인 방식으로 풀었지만, 재귀적인 방식이 아닌 stack을 이용해서 풀 경우 방문 처리를 제대로 해주지않으면 재귀적인 방식과 방문 순서가 ..
그래프(graph)
목차 그래프의 정의 그래프의 분류 그래프의 표현 그래프와 BFS 그래프와 DFS 1. 그래프의 정의 자료구조에서 의미하는 그래프는 다음과 같은 형태이다. 점을 정점(vertex/node)라고 부르고 점을 이어주는 선을 간선(edge)라고 부른다. 그리고, 각 정점에 연결되어있는 간선의 갯수를 차수(degree)라고 한다. 2. 그래프의 분류 - 무방향그래프와 방향그래프 위의 그림과 같이 그래프를 분류할 수 있다. 그래프의 간선에 방향이 없을 경우 무방향 그래프(undirected graph)라고 부르고, 아래와 같이 방향이 있을 경우에는 방향 그래프(directed graph)라고 한다. 이때, 방향 그래프에서 정점에서 나가는 간선의 수를 outdegree, 들어오는 간선의 수를 indegree라고 한다..