사이클

[백준 16929] Two Dots C++

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net DFS 1. 문제해결 아이디어 DFS를 통해서 사이클을 찾는 문제이다. 시작 알파벳과 같은 칸만 이동하며 시작 좌표에 다시 돌아올 때까지 or 돌아오지 못할 때까지 dfs 를 돌린다. 하나의 dfs루프에서 방문한 점을 backtracking 하지 않고 방문처리 기록을 남겨둔다. 2. 코드 : dfs를 돌면서 방문을 했거나 시작점으로 지목된 점에 방문을 한 경우 + 현재 점이 시작점이 아닌경우 (시작하자마자 return 되는것 방지) 1 2 3 4 5 6 ..

[백준 9466] 텀프로젝트 C++

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 를 이용해서 사이클을 이루는지 확인하는 문제 사이클을 찾는 문제다 보니 처음에 union-find를 사용해서 풀었다.. 결과는 시간초과! 틀린 코드 더보기 #include using namespace std; int student[100001]; bool visited[100001]; int makeUnion(int st, int p){ if(student[p] == st) return student[p] = 0; return student[p] = makeU..