PS

문제 링크 : https://www.acmicpc.net/problem/2252 이 문제에서는 출력 조건에 답이 여러 가지인 경우에는 아무거나 출력한다는 것을 보고위상정렬 알고리즘을 사용한다는 것을 유추해 내면 이후에는 단순 알고리즘 구현문제로 바뀌게 된다. 먼저 위상정렬을 사용하려면 진입 차수에 대해 알아야 한다.진입 차수란 그래프로 표현했을때 자신에게 들어오는 간선의 개수이다.예제 입력 1번을 예로 살펴보면d (진입 차수 배열), List (인접 리스트)로 표현할 수 있다. 이때 위상정렬 알고리즘을 사용하려면 아래와 같이 하면 된다.Queue에는 진입 차수가 0인 정점들을 채워준다.이후 q에서 하나씩 빼면서 해당 정점을 출력해주고해당 정점과 인접한 정점의 진입 차수를 하나씩 빼준다. 1번 예제에서는 ..

문제 링크 : https://www.acmicpc.net/problem/1043 문제를 살펴보면 처음에는 단순히 진실을 말해야 하는 사람들이 포함되어 있는 파티에 참여한 모든 사람들에게만진실을 말해야 한다고 생각할 수 있다. 위의 예제는 보면 진실되게 말해야만 하는 사람이 포함되어있지 않은 상태이다.이럴 때는 모든 파티에서 과장되게 말해도 된다.이번에는 예제 5번을 보자여기서 1, 2, 3, 4번은 이미 진실을 알고 있는 사람들이다.따라서 첫 번째 파티의 참여한 1, 5번 중 5번은 진실을 모르는 사람이지만 1번이 포함되어있기때문에 지민이는 진실을 말해야 하고 따라서 5번도 진실을 알게된 사람이 된다.  만약 5번이 임의의 파티에 참석했다고 가정하자해당 파티에는 이미 진실을 알고 있는 1, 2, 3, 4..

문제 링크 : https://www.acmicpc.net/problem/1976 해당 문제는 유니온 파인드를 사용해야 한다는 것만 알아차리면나머지는 유니온 파인드를 구현하는 문제이기 때문에 쉽게 해결할 수 있다. 처음에는 각각의 노드의 집합의 대표노드는 자기 자신인 상태를 만든다.이후 문제에서 들어오는 입력을 잘 받아 union 메서드를 호출한다. 예제의 입력대로 1번 노드와 2번 노드가 이어져있기 때문에2번 노드가 속한 집합의 대표노드를 1로 변경해준다. 이후 들어온 입력값으로 3번 노드는 2번 노드와 이어져있으니여기서도 3번 노드가 속한 집합의 대표노드를 1로 변경해 준다. 마지막에 들어오는 입력값을 통해 목적지로 가려고 하는 곳들의대표노드를 검사하여 모두 동일한 집합이라는 것을 확인하면"YES" 다..

문제 링크 : https://www.acmicpc.net/problem/1717 해당 문제는 유니온 파인드의 대표유형 같은 문제이다.예제를 따라가며 유니온 파인드를 구현해보자. 먼저 예제에 나온 대로 0부터 7까지의 노드가 있다고 할 때각각 자신이 속한 집단의 대표노드가 된다. 그럼 위와 같이 n+1 개의 집합으로 초기화된다. 첫 번째 입력값인 0 1 3을 받았을 때는 1과 3이 속한 집합을 하나로 합쳐야 한다.초기에는 1과 3번 노드 집합의 대표노드가 각각 1과 3이므로 3의 대표집합을 1로 변경해 주면 된다.그다음 입력값인 1 1 7은 1번과 7번이 같은 집합임을 묻는데 확인해 보면 서로대표 노드가 다르므로 NO를 출력해 주면 된다. 다음 입력인 0 7 6도 마찬가지로 각각의 노드가 속한 집합의 대표..