📝 알고리즘/GraphTraversal

문제 https://leetcode.com/problems/find-eventual-safe-states/description/ 각 노드의 라벨이 0부터 n-1까지 붙어있는 n개의 노드로 이루어진 방향 그래프가 있다. 그래프는 0-indexed 인 이차원 정수 배열 `graph`로 표현되고, graph[i]는 노드 i와 인접한 정수 배열이다. 즉, 노드 i로부터 grape[i]에 있는 노드들 간에는 간선이 존재한다. 만약 한 노드에서 나가는 간선이 없다면 해당 노드는 terminal node이다. 한 노드가 safe node라는 것은 해당 노드로부터 시작하는 모든 가능한 경로가 terminal node 혹은 다른 safe node로 이어진다는 것이다. 그래프의 모든 safe node를 포함하는 배열을 ..

문제 (Gold 3) https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 풀이 탐색을 언제, 어디에서 하는지가 굉장히 중요한 문제! 우선, 더 이상 상태 변경이 없을 때까지 탐색을 반복한다. 탐색 코드 cangoTmp: 탐색하기 전의 상태를 저장해 놓는다. 탐색한 곳에서 스위치를 켤 수 있는 곳의 cango값을 true로 변경한다. BFS 탐색을 돌고, 탐색한 곳에서 map의 List를 돌며 계..

문제 (Gold 4) https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 풀이 문제 해석 1. 일반 목초지 사이는 상하좌우 모두 움직일 수 있다. 2. 중간에 다리가 있다면, 다리를 꼭 건너야 한다. 즉, 소(2,2)는 소(2,3)까지 다리를 건너야할 수도 있지만, 그 길을 회피해 회색 화살표 길로 갈 수 있다. 소(3,3)은 다른 목초지에 가려면 무조건 다리를 건너야 하므로, 모든 소와 유효한 쌍이 된다..

문제 (Silver 2) https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 1. 양 또는 늑대가 있는 영역을 검사 (BFS) 2. 그래프를 돌며 양과 늑대의 위치 저장 3. 탐색 후, 양과 늑대 리스트 크기 비교 후 map에 반영 코드 더보기 import java.util.*; import java.io.*; public class Main { static int[] di = {-1,0,1,0}; static int[] dj =..