백준 9466번 링크 문제 풀이 Cycle을 찾는다는 점에서 그래프 문제처럼 생겼지만, 그래프 형태가 워낙 단순해서 스택 문제라고 생각해도 될 것 같다. 사실 DFS나 스택이나 뭐... 같은 방식이니 다른 분들과 다 비슷하게 푼 것 같다. 각 vertex는 directed edge를 하나씩만 가지므로 그래프도 단순하게 int형 배열로 선언한다. visited를 int형으로 선언한 것이 이 문제를 풀 때 유일한 아이디어?라고 할 수 있을 것 같다. 모든 vertex가 연결되어 있지 않은 그래프에서, 모든 vertex에 대해서 DFS를 진행할 때 각 vertex를 방문한 적이 있는지 확인한다. 이때, cnt라는 int형 변수의 값을 1씩 증가시키고, 이번 DFS에서 방문하는 모든 점들의 visited 값은 cnt로 설정한다. 이렇게 하면 몇번째 DFS에서 방문된 vertex인지 확인이 가능하다. Cyc

백준 9328번 링크 문제 풀이 조건이 많아서 BFS 문제처럼 생기긴 했는데 어떻게 풀어야 하나... 고민하다가 main queue, sub queue를 만드는 방식을 생각해냈다. 자료구조 Main queue는 일반적인 BFS에서 사용하는 queue다. Sub queue는 아직 열쇠가 없어서 방문한 적은 있지만, BFS를 수행하지는 못한 cell을 저장한다. 열쇠를 찾았을 때는 sub queue에 있는 모든 cell에 대해 BFS를 수행하면 된다! 열쇠는 'a' ~ 'z'까지 있으므로 sub queue를 총 26개 선언하면 된다. BFS이므로 방문 여부를 저장하기위해 visited 배열을 선언한다. 열쇠 획득 여부를 판단하기 위해 key 배열을 선언한다. 디버깅 checkCell() 함수 visitedr, 즉 방문여부를 확인하는 코드를 넣지 않아 수정했다. 열쇠를

링크텍스트 풀이 방법 Topological sort를 이용한다. 각 학생을 vertex로 보고, 각 규칙을 directed edge로 볼 수 있다. 결과는 규칙을 만족하는 결과를 요구하므로, 모든 edge의 방향성을 만족하는 topological sort가 적절하다. Topological Sort Topological sort의 원리는 다음과 같다. SCC(Strongly connected component) detecting을 한다. SCC는 directed graph에서 모든 정점으로부터 다른 정점까지의 경로가 있는 정점의 집합을 의미한다. SCC 내에는 cycle이 있기 때문에, 모든 directed edge를 만족하는 순서에 따라 sort를 할 수 없다. 즉, SCC가 있는 경우에는 topological sort를 할 수 없다. DFS를 한다. DFS가 끝난 ve