풀이 dfs 문제이다. 테트로미노들은 모두 4칸으로 이루어져있고, 사실상 dfs depth를 4로 했을 때 갈 수 있는 최대값이 도형들의 모양이 되는 것을 확인할 수 있다. 따라서 dfs를 depth 4로 해서 최대값을 구현하면 된다. 배열에 있는 모든 점에 대해서 수행을 해야한다. 그리고 ㅗ 모양에 대해서는 완전 탐색으로 구현하면 된다 for (int i = 0;i < N;i++) { for (int j = 0;j < M;j++) { visited[i][j] = 1; dfs(j, i, 1, arr[i][j]); visited[i][j] = 0; check(j, i); } } 메인함수의 일부분이다. 이 함수를 보면, dfs를 통해서 depth 4인 탐색을 수행한다. check는 매뉴얼하게 ㅗ 모양의 도형..

문병로 교수님의 '관계 중심의 사고법 쉽게 배우는 알고리즘 개정판'을 보고 작성합니다. 1. 연결리스트를 이용한 집합의 처리 연결리스트를 이용해 집합을 처리하면 각 원소당 하나의 노드를 만들고 이들을 연결리스트로 연결한다. 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두개의 포인터가 있습니다. 각 집합의 대표원소는 연결 리스트의 맨 앞에 있는 원소가 된다. 각 집합은 tail이라는 변수를 갖고 있다. 상호배타적 집합의 관리를 위해 세가지 연산이 필요하다. 1. Make-Set(x) : 원소 x로만 구성된 집합을 만든다 - 상수시간이 든다 2. Find-Set(x) : 원소 x를 가진 집합을 알아낸다 - 역시 상수 시간이 든다. (정상수) 왜 상수 시간이 드냐면 Find-Set은 ..