devlog

그래프에서 사이클이 존재하는지 여부는 dfs 를 사용해서 직관적으로 찾을 수 있다. 일반적인 그래프의 코드를 살펴보도록 하자 static void dfs(int v) { visit[v] = true; for(int u : adj[v]) { if(visit[u]) continue; dfs(u); } } v 라는 정점을 기준으로 dfs 를 수행한다고 했을 때 dfs(v) 가 끝나기 전에 v 를 재방문하는 일이 생기면 사이클이 존재함을 알 수 있다. 아래의 코드는 dfs 를 이용한 사이클 존재 여부를 확인하는 코드이다. static boolean cycle = false; static boolean[] visit = new boolean[n+1]; static boolean[] finished = new bo..

문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작�� www.acmicpc.net 해설 조금 까다로운 백트래킹 문제 입니다. 문제를 살펴보면 문제에서 주어진 조건은 다음과 같습니다. 1. 총 7명의 학생들로 구성되어야 하며 2. S가 항상 4개 이상인 조합으로 구성되어야 한다, 반대로 Y는 항상 3개 이하여야 한다. 3. 강한 결속력을 위해 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다. 이렇게 보면 일반적인 DFS, 백 트래킹 문제라고 볼 수 있지만 이 문..

문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 해설 이 문제를 처음 위상 정렬 문제로 생각하고 접근하였는데 단순한 위상 정렬의 개념으로는 풀 수 없는 문제 였습니다. 학생의 키가 몇 번째 인지 알 수있는 학생은 어떻게 구할 수 있을까요? 단순하게 생각해서 해당 학생의 키 순서를 알기 위해서는 그 학생보다 키가 작은학생들과 큰 학생들을 모두 알아야 합니다. 즉, 주어진 학생들 과의 관계를 모두 알 수있을 때 비로소 자신의 키가 몇 번째 인지..