https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 이 문제는 상당히 생각하기 어렵다... 처음에는 어떻게 접근해야 하는지조차 몰랐었다.. 그래서 주변에 물어봐서 이해했다. tree-dp를 처음 풀어본 문제는 아래의 문제였다. https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1..
https://www.acmicpc.net/problem/17352 union_root(1,3)-> parent = [0,2,3,3,4] 부모 노드를 정의한다. find_root(1) -> [0, 3, 3, 3, 4] find_root(2) -> [0, 3, 3, 3, 4]으로 정의되어서 1과 4의 root가 달라서 1 4를 출력한다. public void union_root(int x, int y){ x=find_root(x); y=find_root(y); if(x!=y){ parent[x]=y; } } public int find_root(int x){ if(x==parent[x]) return x; return parent[x]=find_root(parent[x]); } 그래서 union_root는..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이 문제는 너무 어려웠다.. 그래서 결국 해설을 봤다.. 처음에 내가 구현한 방법은 단순히 모든 DFS를 다 돌아서 사이클을 찾아내는 방식으로 했다. 그래서 시간초과가 났다. 그래서 시간초과를 해결하기 위해서는 사이클이 있는 경우 사이클을 이루는 갯수를 세고, 이 과정에서 사용한 노드는 더 이상방문할 필요없는 노드로 처리하여 중복적으로 탐색하는 것을 막아야 했다. 예를 들어 2->1->3->3과 1->..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 나는 처음에 이 문제에서 주어진 이분 그래프가 뭔지 잘 이해하지 못했다. 그래서 구글링을 통해 위키백과에 정의 된 그림도 봐보고 다른 사람들의 설명도 봐보았다. 문제에 주어진 아래와 같은 설명은 나같은 감자에게는 이해하기 어렵다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Gr..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 2667번과 거의 동일하다. 다른 점이라면 테스트 케이스를 입력 받은만큼 실행한다는 것과, 배추가 있는 좌표를 찍어야 한다는 점 정도이다. 나머지는 2667번과 동일하게 DFS,BFS 모두로 풀 수 있을 것이다. 풀이 방법은 먼저 테스트 케이스를 몇 개 실행할지 입력 받는다. 그 다음에 가로 길이 M과 세로 길이 N을 입력 받고 배추의 갯수인 K를 입력받는다. 그 다음 아래 K개의 줄에 배추가 있는..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이 문제는 조금 헷갈리는 부분이 있었다. 1인 부분에 대해서 탐색을 모두 해야하는데 그걸 어떤식으로 해서 반복해야하는지 막막한 부분이 있었는데, 질문 게시판에서 그에 대한 해결책을 얻었다. 방법은 주어진 단지 테이블에서 각각의 위치마다 1인것에 대해 DFS나 BFS를 통해 탐색을 진행하는 방식으로 하면 된다는 것을 알았다. 즉, 단지 테이블에 1인 지점이 나오면 이에 대해 탐색을 진행하고, 탐색이 ..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이번에는 BFS와 DFS 중에 선택하여 푸는 문제를 풀어보았다. 나는 우선 BFS에 대해 공부하기 위해서 BFS로 풀었다. 그리고 문제를 생각했을 때 DFS보다는 BFS가 접합하다고 생각했다. 왜냐하면 시작 노드와 근접한 모든 노드를 찾는 것이기 때문에 DFS로 하나의 노드에 대해서 계속 찾아갔다가 돌아오는 방식은 오래걸릴 것 같아서이다. 또한 잘못하여 노드의 깊이가 너무 깊을 경우 시간 초과가 발생할..
https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 저번에 이어서 DFS기초 문제를 다시 풀어보았다. 저번과 같은 코드이지만 내림차순이어서 인접 리스트의 정렬을 내림차순으로 바꿔주기만 하면 된다. 너무 간단한 문제여서 오늘은 짧게 설명하겠다. 방문 여부를 판단하는 boolean배열과 순서를 담을 int배열 그리고 순서값을 셀 count 그리고 node의 갯수가 있으면, boo..
