dfs3 [백준] 2583 - 영역 구하기 (Python) 문제 출처 : www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 풀이 : 맵을 생성한다 이후 주어지는 패치에 대해서 map 값을 1로 바꿔준다. 이후 모든 패치가 붙여진 map에 대해서 순회를 돌면서 0값이 있을때는 DFS()를 수행하며 0값이 있었던 블록과 붙어있는 넓이를 구한다. 이후 넓이를 area 리스트에 넣어놓고 모든 맵이 순회가 끝나면, 정렬 후 정답을 출력한다. m,n,k = map(int,input().split()) m.. 2021. 3. 17. [백준] 10451 - 순열 사이클 (Python) 문제 출처 : www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 문제 풀이 : DFS로 풀면 각 cycle이 나올때마다 방문 표시를 해주고, 전체 (모든 노드를 통과하는) 반복문에서는 방문 표시가 있을때는 DFS를 하지 않도록 한다면 추가로 cycle을 구분해 주지 않아도 각 싸이클에서만 ans을 더해줄 수 있다. 이 문제는 cycle이 정확하기 때문에 (어디서 시작하고 어디서 끝날지 우.. 2021. 3. 12. [백준] 9466 - 텀 프로젝트 (Python) 문제 출처 : www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 풀이: 이 문제는 처음에 각 학생들마다 방문과 싸이클을 따로 구하려고 하다보니 무척 어려웠다. 사실상 이문제는 싸이클을 구하는 문제 인데, 싸이클의 핵심은 node가 root를 가르키면 된다는 점이다. 이점을 고안해서 dfs를 사용하면 해결된다. 코드에선 방문 하지 않은 경우에는 team을 리스트 변수로 생성하고(이건 추후에 cycle 후보들이 담긴다), 그후 dfs 함수를 호출한다. dfs 함수.. 2021. 3. 12. 이전 1 다음 반응형
