Algorithm/그래프
-
백준 14940 쉬운 최단거리Algorithm/그래프 2022. 1. 5. 21:26
https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net - 간단한 그래프 탐색 문제이다. 시간복잡도는 한 번의 bfs가 실행되므로 O(MN) - M과 N이 최대 1000이므로, 모든 칸에 대해서 bfs를 실행한다면 시간초과가 나게 된다. 따라서, 좌표가 2인 칸에서만 bfs를 실행 해 주면 된다. map과 똑같은 크기의 answer배열에 정답을 넣어줄 것이다. - 탐색을 진행할 때 방문하는 노드의 기준은 1..
-
[프로그래머스] 여행 경로Algorithm/그래프 2021. 12. 31. 14:28
https://programmers.co.kr/learn/courses/30/lessons/43164?language=cpp 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr - DFS/BFS 문제이다. - 가장 먼저, dfs를 어떻게 구현 할 지를 생각해야 한다. dfs함수의 매개변수에는 tickets배열, 현재 머무는 공항의 이름, 현재까지의 모든 경로를 문자열로 기록 해 놓은 path, 티켓을 얼마나 사용했는 지를 나타내는 count변수를 사용한다. dfs를 구현하는 경우..
-
백준 10026 적록색약Algorithm/그래프 2021. 12. 10. 15:02
https://www.acmicpc.net/status?user_id=totw2018&problem_id=10026&from_mine=1 채점 현황 www.acmicpc.net - 그래프 탐색 알고리즘 문제이다. 시간복잡도는 그래프 탐색 + 문자 치환 탐색 + 그래프 탐색 해서 총 O(n^2)이다. - 특이하게, 입력을 문자열들로 준다. 따라서 필자는 string 자료형으로 총 n번을 입력받고, 입력 받을 때 마다 문자 하나하나를 char 배열 map에 저장을 했다. 또한, 처음 주어진 map에서 BFS 한 번, 이 후 맵의 G를 모두 R 문자로 바꿔준 다음 또 한 번 BFS를 진행하였다. 이러한 점 외에는 다른 그래프 탐색 문제와 크게 다를 것이 없다. - 여담으로, 15분만에 문제를 풀어내서 뿌듯하다..
-
백준 7569 토마토Algorithm/그래프 2021. 12. 4. 17:38
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net - 그래프 탐색 문제인데, 특이하게도 3차원으로 값이 주어져서 난이도가 조금 올라가는 문제이다. 따라서, 필자는 3차원 배열을 활용하였고 M,N,H를 각각 X,Y,Z로 두어서 계산을 하였다.(각각 행, 열, 높이) - 시간복잡도는 O(MNH)이 나온다. 2차원 그래프탐색을 H번 진행해야 하므로! - 처음에 토마토가 담긴 칸을 queue에 담는다. 또, visited를 0으로..
-
백준 1260 DFS와 BFSAlgorithm/그래프 2021. 11. 13. 12:18
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net - 그래프 알고리즘을 처음 입문할 때 좋은 문제이다. - DFS의 경우, 재귀적으로 구현하는 경우 O(V^2)의 시간복잡도가 나온다. BFS의 경우, 인접 행렬을 사용할 것이므로 O(V^2)의 시간복잡도가 나온다. - 주의해야 할 점은, 무방향 그래프이므로 처음 인접 행렬을 구성할 때 양방향으로 등록을 해 주어야 한다는 것, 또 하나의 노드에서 여러 개의 간선..
-
백준 14502 연구소Algorithm/그래프 2021. 11. 12. 20:14
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net - N과 M이 최대 2^3이므로, 많은 for문을 중첩시킬 수 있다. (NM = n || ny >= m) continue; if (virus[nx][ny] == 0) { virus[nx][ny] = 2; visited[nx][ny] = true; q.push({ nx,ny }); } } } // 안전구역 검사 후, answer 최신화 int cnt = 0; for (int i = 0; i < n; i++) {..