자신 또는 바로 이웃한 노드가 얼리어답터가 되는 노드를 찾는다면, 어떤 노드가 얼리어답터가 되어야 하는지 알 수 있다.
즉, 종단 노드를 찾으면, 종단노드의 이웃 노드는 반드시 얼리어답터가 되어야 한다.
종단 노드가 얼리어답터가 되는 것은, 이웃 노드가 얼리어답터가 되는 것 보다 비효율적인데,
종단 노드는 하나의 노드에만 연결 되어 있는 반면, 이웃 노드는 최소 2개의 노드와 연결 되어있기 때문이다.
즉, 영향을 미칠 수 있는 범위가 다르다는 것이다.
그럼 먼저 종단노드를 찾고, 얼리어답터를 선정해보자.
3, 6, 7, 8, 10은 각각 종단 노드이다. 각각 표시를 해 놓겠다.
먼저 가장 처음 발견한 종단 노드인 3번 노드를 보자. 위에서 설명한 바와 같이 종단 노드가 얼리어답터가 되는 것 보다, 그 이웃노드가 얼리어답터가 되는 것이 좋다. 고로 1을 얼리어답터로 선정한다.
그 다음 종단 노드들에 대해서도 차례로 이웃 노드를 얼리어답터로 선정한다.
이제 기존의 종단 노드들은 고려하지 않아도 된다. 종단 노드들을 지워보자.
종단 노드는 4, 9번 노드이다.
4번 9번 노드는 모두 얼리어답터이므로, 다음 노드를 불필요하게 얼리어답터로 만들 필요가 없다. 다시 종단 노드들을 지워보자.
1번, 5번 노드가 종단 노드가 되었다.
1번 노드는 얼리어답터이므로, 다음 노드를 얼리어답터로 만들 필요가 없다. 5번 노드의 이웃 노드는 이미 얼리어답터이다. 다시 종단 노드를 지워보자.
2번 노드는 종단 노드이지만 이웃 노드가 없다.
그렇다면, 모든 노드와 그 이웃 노드를 살펴봤다고 볼 수 있을 것이다. 이렇게 종단노드를 옮겨가며 그 이웃노드를 얼리어답터로 만든 결과 아래와 같이 얼리 어답터가 나온다.
1, 2, 4, 9번 노드가 얼리어답터가 되었고, 위보다 더 적은 얼리어답터가 나오는 경우는 없다. 즉, 답은 4이다.
위 과정을 보았을때, 풀이 과정은 다음과 같을 것이다.
종단 노드를 찾는다.
종단 노드의 이웃 노드를 얼리어답터로 만든다. 동시에 총 얼리어답터 수를 1 늘리며, 이때, 중복에 유의한다.
종단 노드의 이웃 노드가 얼리어답터가 되며, 동시에 종단 노드가 된다.
종단 노드가 얼리어답터라면, 이웃노드는 얼리어답터가 아니고, 이웃 노드가 종단 노드가 된다.
위 과정을 반복하고, 이웃이 없는 종단 노드가 나온다면, 얼리어답터 수를 반환한다.
더 간결하게 말하자면,
종단 노드를 찾는다.
종단 노드와 이웃 노드가 얼리어답터가 아니라면, 이웃 노드를 얼리어답터로 만든다. 동시에 총 얼리어답터 수를 1 늘리며, 이때, 중복에 유의한다. 이웃 노드가 종단 노드가 된다.
1, 2번 과정을 반복하고, 이웃이 없는 종단 노드가 나온다면, 얼리어답터 수를 반환한다.
각 노드를 나타내는 클래스를 만들어서 풀어보도록 하겠다.
class Friend {
private boolean visited;
private boolean earlyAdaptor;
private int friendsNumber;
private List<Friend> friendList;
public Friend() {
visited = false;
earlyAdaptor = false;
friendsNumber = 0;
friendList = new ArrayList<>();
}
}
visited는 방문 여부를 나타낸다. 중복 방문을 막기 위해서이다.
earlyAdaptor은 얼리어답터인지 아닌지 나타낸다.
friendsNumber는 이웃노드의 수를 나타내며, 1이라면 종단노드이다.
friendList는 이웃노드들을 나타낸다.
static int earlyAdapterCount(List<Friend> friendList) {
int count = 0;
Queue<Friend> queue = new LinkedList<>();
for (Friend friend : friendList) {
if (friend.isLastNode()) {
queue.add(friend);
}
}
while (!queue.isEmpty()) {
Friend friend = queue.poll();
friend.setVisited(); // 다시 방문하지 않도록 표시
Friend nextNode = friend.removeLastNode();
if (nextNode == null) {
break;
}
if (friend.becomeEarlyAdopter(nextNode)) {
count++;
}
if (nextNode.isLastNode()) {
queue.add(nextNode);
}
}
return count;
}
주요 기능을 수행하는 메서드이다.
종단 노드를 찾는다.(isLastNode 메서드) 해당 종단 노드를 queue에 저장한다.
queue에 데이터가 있는 동안 아래 과정을 반복한다.
queue에서 종단 노드를 꺼낸다. 종단 노드에 다시 방문하지 않도록 표시한다.(setVisited)
종단 노드를 지우며 이웃 노드를 반환받는다. 비순환 그래프의 종단 노드의 특성상 반드시 1 또는 0개의 이웃 노드를 가진다.
이웃 노드가 없다면, 즉 이미 트리를 모두 살펴봤다면, 반복문을 종료한다.
만약 이웃 노드가 얼리어답터가 될 수 있다면, 총 얼리어답터의 수 +1을 해준다.
만약 이웃 노드가 종단 노드가 될 수 있다면(1개의 이웃 노드를 가짐), 종단 노드를 나타내는 queue에 이웃 노드를 저장한다.
반복문이 종료되면, 그동안 구한 얼리어답터의 수를 반환한다.
위 주요 메서드를 수행하기 위해서는 아래와 같은 클래스 변수가 필요하다.
public boolean isVisited() {
return visited;
}
private boolean isEarlyAdaptor() {
return earlyAdaptor;
}
public void setVisited() {
visited = true;
}
private void setEarlyAdaptor() {
earlyAdaptor = true;
}
public boolean isLastNode() {
return friendsNumber == 1;
}
private List<Friend> getFriendList() {
return friendList;
}
public void addFriend(Friend friend) {
friendList.add(friend);
friendsNumber++;
friend.friendList.add(this);
friend.friendsNumber++;
}
// 마지막 노드의 친구가 얼리어답터가 될 수 있는지 판정해서 될 수 있다면 true, 없다면 false 반환
public boolean becomeEarlyAdopter(Friend friend) {
if (!friend.isEarlyAdaptor() && !this.isEarlyAdaptor()) { // 둘다 얼리어답터가 아니라면 하나는 무조건 얼리아답터
friend.setEarlyAdaptor();
return true;
}
return false;
}
public Friend removeLastNode() {
for(Friend friend : this.getFriendList()) { // 자신과 연결된 노드들 순회
if (!friend.isVisited()) { // 만일 이미 처리된 노드라면 다시 처리해줄 필요 없음
friendsNumber--;
friend.friendsNumber--;
return friend;
}
}
return null;
}
위 메서드들은 메서드명과 동일한 기능을 한다.
중요한 두 메서드만 설명하겠다.
becomeEarlyAdopter 마지막 노드의 이웃노드가 얼리어답터가 될 수 있는지 판단한다.
removeLastNode 자신과 연결된 노드들을 순회해서, 방문 기록이 없는 종단 노드만 제거 할 수 있도록 한다. 이미 제거된 노드들을 고려하지 않기 위해 방문 기록을 이용했다.
이렇게 하면 클래스를 이용해 문제를 풀 수 있을 것이다.
전체코드:
import java.io.*;
import java.util.*;
class Friend {
private boolean visited;
private boolean earlyAdaptor;
private int friendsNumber;
private List<Friend> friendList;
public Friend() {
visited = false;
earlyAdaptor = false;
friendsNumber = 0;
friendList = new ArrayList<>();
}
public boolean isVisited() {
return visited;
}
private boolean isEarlyAdaptor() {
return earlyAdaptor;
}
public void setVisited() {
visited = true;
}
private void setEarlyAdaptor() {
earlyAdaptor = true;
}
public boolean isLastNode() {
return friendsNumber == 1;
}
private List<Friend> getFriendList() {
return friendList;
}
public void addFriend(Friend friend) {
friendList.add(friend);
friendsNumber++;
friend.friendList.add(this);
friend.friendsNumber++;
}
// 마지막 노드의 친구가 얼리어답터가 될 수 있는지 판정해서 될 수 있다면 true, 없다면 false 반환
public boolean becomeEarlyAdopter(Friend friend) {
if (!friend.isEarlyAdaptor() && !this.isEarlyAdaptor()) { // 둘다 얼리어답터가 아니라면 하나는 무조건 얼리아답터
friend.setEarlyAdaptor();
return true;
}
return false;
}
public Friend removeLastNode() {
for(Friend friend : this.getFriendList()) { // 자신과 연결된 노드들 순회
if (!friend.isVisited()) { // 만일 이미 처리된 노드라면 다시 처리해줄 필요 없음
friendsNumber--;
friend.friendsNumber--;
return friend;
}
}
return null;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
List<Friend> friendList = new ArrayList<>();
friendList.add(new Friend());
for (int i = 1; i <= N; i++) {
friendList.add(new Friend());
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
friendList.get(u).addFriend(friendList.get(v));
}
System.out.println(earlyAdapterCount(friendList));
}
static int earlyAdapterCount(List<Friend> friendList) {
int count = 0;
Queue<Friend> queue = new LinkedList<>();
for (Friend friend : friendList) {
if (friend.isLastNode()) {
queue.add(friend);
}
}
while (!queue.isEmpty()) {
Friend friend = queue.poll();
friend.setVisited(); // 다시 방문하지 않도록 표시
Friend nextNode = friend.removeLastNode();
if (nextNode == null) {
break;
}
if (friend.becomeEarlyAdopter(nextNode)) {
count++;
}
if (nextNode.isLastNode()) {
queue.add(nextNode);
}
}
return count;
}
}
시행착오:
찾아보면 알겠지만, dp를 이용해서 푸는 풀이가 더 간결하다.
하지만 위의 풀이도 방문 기록을 이용하고, 사람에 따라 더 가독성이 좋다고 생각한다.
그래도 훨씬 간결한 dp로도 한번 풀어봐야겠다.
위 코드를 작성하며, 처음에는 List에 저장된 요소들을 지워, 방문 기록 자체를 따로 저장하지 않았다.
하지만, List에 저장된 요소를 지우며, 문제를 풀다보니 ConcurrentModificationException이 발생했다.
