DFS

DFS, 인접행렬, 역행렬을 사용하는 문제이다. Candidate | Softeer Assessment UI softeer.aiS -> T로 가는 경로가 존재해야 하고,T -> S로 돌아오는 경로가 존재해야 한다.fromS와 fromT만 사용하면 S -> T와 T -> S 경로를 독립적으로 찾게 되며, 이는 각각의 경로가 서로 다른 노드를 포함할 수 있다. 예를 들어, S -> T 경로가 포함하는 노드가 T -> S 경로와 일치하지 않을 수 있다. 그래서 역행렬이 알고리즘이 필요하다. fromS: S에서 출발하여 도달할 수 있는 모든 노드.fromT: T에서 출발하여 도달할 수 있는 모든 노드.toS: S로 도달할 수 있는 모든 노드 (역방향 그래프).toT: T로 도달할 수 있는 모든 노드 (역방향 그..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에www.acmicpc.net풀이과정처음에는 단순하게 DFS 재귀 백트래킹을 이용하여 구현했다.하지만, DP를 사용하지 않으면 시간초과가 났다. 괜히 골드3 문제가 아니다.DP와 DFS를 같이 사용해야 하는 새로운 문제 유형이었다.만약 이 그림 (0, 0)에 판다를 냅둔다면, (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) 을 통해서 총 5일을 살게 될 것이다. 그럼 dp[0][0] ..