99클럽 코테 스터디 4일차 TIL: DFS

문제

https://www.acmicpc.net/problem/24479

 

풀이

오늘은 챌린저 문제가 아닌 미들러 문제를 풀었다.
그 이유는 챌린저 문제를 1시간안에 풀어보려 했지만 풀이하지 못했다.
힌트를 확인해보니 벨만포드 알고리즘이였고,
벨만포드 알고리즘 하면 기억나는데 음의간선에서도 최단거리를 구할 수 있다는점..? 그래서 사이클이 존재하면 안된다는 점 밖에 기억이 나지 않았다..

그래서 일단은 미들러 문제를 풀고, 주말에 벨만포드 알고리즘에 대해 더 학습하고 풀어야겠다고 생각했다.

미들러문제는 DFS의 기본적인 문제였고, 챌린저 문제와 난이도 차이가 있다고 느꼈다.
DFS에 대해 알고, 조금만 응용한다면 쉽게 풀 수있다.

방문 여부를 확인하는 visited 배열을 Int로 사용하였고, 0일 때는 아직 방문하지 않은 것, 그 이후 자연수는 방문한 Depth로 두었다.

소스코드

후기

갑자기 챌린저 문제가 어려웠다.. 주말에 꼭 풀어봐야지..