두 자연수 X와 K가 주어진다. 그러면, 다음 식을 만족하는 K번째로 작은 자연수 Y를 구하는 문제이다.

X + Y = X | Y

 

| 가 OR 비트연산이므로 2진수로 생각해보자.

 

예제 X = 5 = 101(2)

101 + Y = 101 | Y 의 경우 X의 0이 있는 부분이 1인 경우 Y가 된다. 가능한 Y값을 크기순으로 나열하면 아래와 같다.

문제 풀이 방법은 위와 같이 X가 1, 0인 부분을 저장해 두고 1인 부분은 건너뛰면서 다음으로 가능한 수를 찾아준다.

y 값은 1을 넘어갈 수 있다고 했으니 long 범위로 설정해준다면 8byte = 64bit일 것이고, 이를 배열에 담아준다.

 

x, k를 2진수로 바꿔서 배열에 거꾸로 저장한 후 0인 비트를 해당 자리 수 만큼 쉬프트한다.

이를 구현한 코드는 아래와 같다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long x = in.nextLong();
		long k = in.nextLong();

		int binX[] = new int[65];
		int binK[] = new int[65];

		int i = 0;

		while (x != 0 || k != 0) {
			binX[i] = (int) (x % 2);
			binK[i] = (int) (k % 2);
			x /= 2;
			k /= 2;
			i++;
		}

		int xIndex = 0, kIndex = 0;
		long y = 0;

		while (kIndex < i) {
			if (binX[xIndex] == 0) {
				y |= (1L << xIndex) * binK[kIndex++];
			}
			xIndex++;
		}

		System.out.println(y);
	}
}

 

'알고리즘 공부 > boj' 카테고리의 다른 글

boj 1027: 고층 건물  (0) 2021.02.02
boj 17071: 숨바꼭질 5  (0) 2021.01.31
boj 1294: 문자열 장식  (0) 2021.01.29
boj 16637: 괄호 추가하기  (0) 2021.01.27
boj 1167: 트리의 지름  (0) 2021.01.25

문자열을 적절히 쪼갠 후 하나로 합칠 때, 사전상으로 가장 앞에 오는 단어를 구하는 문제이다.

한 문자내의 쪼갠 문자 순서는 바뀌면 안된다

 

먼저 아이디어는 각 단어를 가리키는 포인터가 각각 존재하며,

맨 앞부분만 서로 비교했을 때 가장 작은 값을 stringbuilder에 하나씩 붙인다.

 

처음에는 단순히 사전순, 길이순으로 정렬해서 풀었는데, 이 경우는 ABCCC, BACCC인 경우 ABABCCCCCC 예외케이스가 나온다.

이는 BAA, BA 테스트 케이스를 해결하기 위해 문자열의 길이를 함께 봤기 때문에 생긴 예외케이스이다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		List<String> string = new ArrayList<String>();
		int index[] = new int[n];
		int length[] = new int[n];

		PriorityQueue<Alphabet> queue = new PriorityQueue<Alphabet>();
		for (int i = 0; i < n; i++) {
			string.add(in.next());
		}
		string.sort(Comparator.comparing(String::length).reversed().thenComparing(String::compareTo));

		for (int i = 0; i < n; i++) {
			queue.add(new Alphabet(i, string.get(i).charAt(index[i])));
			length[i] = string.get(i).length();
		}

		StringBuilder sb = new StringBuilder("");
		while (!queue.isEmpty()) {
			Alphabet alphabet = queue.poll();

			sb.append(alphabet.ch);

			int nextIndex = alphabet.index;
			if (index[nextIndex] < length[nextIndex] - 1) {
				index[nextIndex]++;
				queue.add(new Alphabet(nextIndex, string.get(nextIndex).charAt(index[nextIndex])));
			}
		}
		System.out.println(sb.toString());
	}
}

class Alphabet implements Comparable<Alphabet> {
	int index;
	char ch;
	int length;

	public Alphabet(int index, char ch) {
		this.index = index;
		this.ch = ch;
	}

	@Override
	public int compareTo(Alphabet o) {
		if (ch == o.ch) {
			return Integer.compare(index, o.index);
		}
		return Character.compare(ch, o.ch);
	}

	@Override
	public String toString() {
		return "(" + index + ", " + ch + ")";
	}
}

 

그렇다면 문자열을 큐에 넣을때마다 정렬해야 한다는 소리인데

문자열 자체를 맨 앞 부분을 하나씩 제거해야하기 때문에,

연산을 할 때마다 새로운 객체를 반환하는 불변객체 String보다는 StringBuffer을 사용했다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		PriorityQueue<StringBuffer> queue = new PriorityQueue<StringBuffer>(new BufferComparator());

		for (int i = 0; i < n; i++) {
			queue.add(new StringBuffer(in.next()));
		}

		while (!queue.isEmpty()) {
			//System.out.println(queue);

			StringBuffer alphabet = queue.poll();

			System.out.print(alphabet.charAt(0));
			alphabet.deleteCharAt(0);

			if (alphabet.length() > 0) {
				queue.add(alphabet);
			}
			alphabet = null;
		}
		System.out.println();
	}
}

class BufferComparator implements Comparator<StringBuffer> {

	public int compare(StringBuffer s1, StringBuffer s2) {
		int min = Math.min(s1.length(), s2.length());
		for (int i = 0; i < min; i++) {
			if (s1.charAt(i) > s2.charAt(i)) {
				return 1;
			} else if (s1.charAt(i) < s2.charAt(i)) {
				return -1;
			}
		}
		return Integer.compare(s2.length(), s1.length());
	}
}

 

BufferComparator을 직접 구현해서 정렬해주도록 했다.

결과는 53%에서 시간초과..

 

 

 

결론적으로는 로직 자체는 같으나, 커스텀 Comparator을 사용하지 않고 기본 Comparable로 정렬하여 사용하는 방법이라면 통과가 된다.

문제 조건에서 공백은 없이 알파벳 대문자로만 구성되어 있다고 했기 때문에,

문자 마지막에 'a'를 붙여주면 (ASCII - \0: 0, a: 097, A: 065)

모든 대문자는 'a'보다 작기 때문에 커스텀 Comparator를 사용하지 않고 기본 Comparable을 사용하면서 같은 동작을 하도록 만들 수 있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		PriorityQueue<StringBuffer> queue = new PriorityQueue<StringBuffer>();
		for (int i = 0; i < n; i++) {
			queue.add(new StringBuffer(in.next() + "a"));
		}

		while (!queue.isEmpty()) {
			StringBuffer alphabet = queue.poll();

			System.out.print(alphabet.charAt(0));
			alphabet.deleteCharAt(0);

			if (alphabet.length() > 1) {
				queue.add(alphabet);
			}
			alphabet = null;
		}
		System.out.println();
	}
}

 

 

이 문제에서 주의해야 하는 대표 테스트케이스는 아래와 같다

4 
CCCA 
CCCB 
CCCD 
CCCE

2
ABCCC
BACCC

2
BAA
BA

 


PriorityQueue의 정렬 방법

PriorityQueue 내부의 정렬은 아래와 같은 함수를 이용하여 정렬된다.

정렬 자체에 영향을 주는 가장 큰 요소는 정렬 알고리즘인데, 이는 머지 소트로 동일하다.

    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x, queue, comparator);
        else
            siftUpComparable(k, x, queue);
    }
    
    private static <T> void siftUpComparable(int k, T x, Object[] es) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = key;
    }

    private static <T> void siftUpUsingComparator(
        int k, T x, Object[] es, Comparator<? super T> cmp) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (cmp.compare(x, (T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = x;
    }

왠지는 모르겠지만.. 아래는 기본 Comparable과 custom Comparator이다.

어디서 차이가 발생했는지 시간날 때 compareTo 함수를 좀 더 까봐야겠다...

    int compareTo(AbstractStringBuilder another) { // StringBuffer::compareTo
        if (this == another) {
            return 0;
        }

        byte val1[] = value;
        byte val2[] = another.value;
        int count1 = this.count;
        int count2 = another.count;

        if (coder == another.coder) {
            return isLatin1() ? StringLatin1.compareTo(val1, val2, count1, count2)
                              : StringUTF16.compareTo(val1, val2, count1, count2);
        }
        return isLatin1() ? StringLatin1.compareToUTF16(val1, val2, count1, count2)
                          : StringUTF16.compareToLatin1(val1, val2, count1, count2);
    }
    
    class BufferComparator implements Comparator<StringBuffer> { // Custom BufferComparator

        public int compare(StringBuffer s1, StringBuffer s2) {
            int min = Math.min(s1.length(), s2.length());
            for (int i = 0; i < min; i++) {
                if (s1.charAt(i) > s2.charAt(i)) {
                    return 1;
                } else if (s1.charAt(i) < s2.charAt(i)) {
                    return -1;
                }
            }
            return Integer.compare(s2.length(), s1.length());
        }
    } 

 

 

'알고리즘 공부 > boj' 카테고리의 다른 글

boj 17071: 숨바꼭질 5  (0) 2021.01.31
boj 1322: X와 K  (0) 2021.01.29
boj 16637: 괄호 추가하기  (0) 2021.01.27
boj 1167: 트리의 지름  (0) 2021.01.25
boj 1939: 중량제한  (0) 2021.01.20

문제 조건

  • 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다.
  • 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. (짝수번째는 숫자, 홀수번째는 연산 기호)
  • 연산자는 +, -, * 중 하나이다.
  • 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다. 단, 괄호는 중첩되면 안된다.

수식의 길이 1 ≤ N ≤ 19이므로 dfs를 이용하여 완전 탐색을 해도 시간 초과가 나지 않을 것이다.

괄호를 묶는 방법은 (a+b)+c, a+(b+c) 두 가지 방법으로 나누어 계산한다.

import java.util.*;

public class Main {
	public static long max = Integer.MIN_VALUE;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String s = in.next();
		char[] expression = s.toCharArray();

		if (n == 1) {
			System.out.println(s);
		} else {
			dfs(expression[0] - '0', 1, expression);
			System.out.println(max);
		}
	}

	public static void dfs(long result, int index, char[] expression) {
		if (index + 1 >= expression.length) {
			max = Math.max(max, result);
			return;
		}

		// (a+b)+...
		long resultFront = calculate(result, expression[index], expression[index + 1]);
		dfs(resultFront, index + 2, expression);

		// a+(b+c)+...
		if (index + 3 < expression.length) {
			long resultBack = calculate(expression[index + 1], expression[index + 2], expression[index + 3]);
			dfs(calculate(result, expression[index], resultBack), index + 4, expression);
		}

	}

	public static long calculate(long a, char op, long b) {
		switch (op) {
		case '*':
			return a * b;
		case '+':
			return a + b;
		case '-':
			return a - b;
		}
		return 0L;
	}

	public static long calculate(long a, char op, char b) {
		return calculate(a, op, (long) (b - '0'));
	}

	public static long calculate(char a, char op, char b) {
		return calculate((long) (a - '0'), op, (long) (b - '0'));
	}
}

'알고리즘 공부 > boj' 카테고리의 다른 글

boj 1322: X와 K  (0) 2021.01.29
boj 1294: 문자열 장식  (0) 2021.01.29
boj 1167: 트리의 지름  (0) 2021.01.25
boj 1939: 중량제한  (0) 2021.01.20
boj 17143: 낚시왕  (0) 2021.01.20

트리의 지름: 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것

 

트리의 지름이라면.. 저번에 풀었던 문제를 함께 보면 좋다.

2020/12/20 - [알고리즘 공부/programmers] - Programmers 68937: 트리 트리오 중간값

 

Programmers 68937: 트리 트리오 중간값

예시 1 답: (트리의 지름) - 1 예시 2 답: (트리의 지름) 1차 시도 - 시간초과 트리의 지름을 가지는 노드가 2쌍 이상이면 2번 예시에 들어가고, 한 쌍이면 1번 예시에 들어가게 된다. 트리의 지름을

sysgongbu.tistory.com

 

어떤 트리의 지름을 구하는 방법을 예시를 통해 보자.

1. 먼저 임의의 점(1)부터 순회를 시작하여 가장 먼 거리에 있는 점 5를 찾는다.

2. 가장 먼 점 5에서 다시 순회를 하면서 가장 먼 거리에 있는 점은 2이며, 5~2=11이 트리의 지름이 된다.

이러한 풀이를 이용하면 모든 점에 대해 가장 먼 거리를 구하지 않아도 되고, 시간복잡도는 O(N)으로 줄어든다. 풀이는 아래와 같다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		LinkedList<Node> connections[] = new LinkedList[v + 1];
		for (int i = 1; i <= v; i++) {
			int start = in.nextInt();
			connections[start] = new LinkedList<Node>();
			
			while (true) {
				int end = in.nextInt();
				if (end == -1) {
					break;
				}
				int length = in.nextInt();

				connections[start].add(new Node(end, length));
			}
		}

		System.out.println(findTreeRadius(1, connections, true, v));
	}

	public static int findTreeRadius(int start, LinkedList<Node> connections[], boolean isFirstCycle, int n) {
		boolean[] isVisited = new boolean[n + 1];

		Queue<Node> queue = new LinkedList<Node>();
		queue.add(new Node(start, 0));
		isVisited[start] = true;

		int maxNode = start;
		int maxLength = 0;
		while (!queue.isEmpty()) {
			Node now = queue.poll();

			if (maxLength < now.length) {
				maxLength = now.length;
				maxNode = now.name;
			}

			for (Node next : connections[now.name]) {
				if (!isVisited[next.name]) {
					queue.add(new Node(next.name, now.length + next.length));
					isVisited[next.name] = true;
				}
			}
		}

		if (isFirstCycle) {
			return findTreeRadius(maxNode, connections, false, n);
		}
		return maxLength;
	}
}

class Node {
	int name;
	int length;

	public Node(int name, int length) {
		this.name = name;
		this.length = length;
	}

	@Override
	public String toString() {
		return "(" + name + ", " + length + ")";
	}
}

 

'알고리즘 공부 > boj' 카테고리의 다른 글

boj 1294: 문자열 장식  (0) 2021.01.29
boj 16637: 괄호 추가하기  (0) 2021.01.27
boj 1939: 중량제한  (0) 2021.01.20
boj 17143: 낚시왕  (0) 2021.01.20
boj 1005: ACM Craft  (0) 2021.01.20

start -> end까지 지나는 다리 각각의 최솟값에 대한 최댓값을 구하는 문제이다.

이분탐색으로 중량을 정해두고 BFS로 다리를 지나갈 수 있는지 확인하면 쉽게 풀리는 문제이다.

 

이렇게 풀 경우 서로 같은 두 도시 사이에 여러 개의 다리가 있다는 조건을 딱히 생각해 줄 필요가 없다.

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		LinkedList<Bridge> bridges[] = new LinkedList[v + 1];
		for (int i = 1; i <= v; i++) {
			bridges[i] = new LinkedList<Bridge>();
		}

		int max = 0;
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int size = in.nextInt();

			max = Math.max(max, size);

			bridges[start].add(new Bridge(end, size));
			bridges[end].add(new Bridge(start, size));
		}

		int start = in.nextInt();
		int end = in.nextInt();

		System.out.println(findMinimumWeight(start, end, bridges, max));
	}

	public static int findMinimumWeight(int from, int to, LinkedList<Bridge> bridges[], int end) {
		boolean[] isVisited = new boolean[bridges.length];

		int start = 0;
		int max = 0;

		while (start <= end) {
			int mid = (start + end) / 2;

			if (BFS(from, to, bridges, mid, isVisited)) { // 가능하니까 일단 결과 저장 후 중량을 더 늘려보자
				max = Math.max(max, mid);
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		return max;
	}

	public static boolean BFS(int start, int end, LinkedList<Bridge> bridges[], int maxSize, boolean[] isVisited) {
		clearVisit(isVisited);

		Queue<Integer> queue = new LinkedList<Integer>();

		queue.add(start);
		isVisited[start] = true;

		while (!queue.isEmpty()) {
			int now = queue.poll();

			if (now == end) {
				return true;
			}

			for (Bridge bridge : bridges[now]) {
				if (!isVisited[bridge.destination] && maxSize <= bridge.size) {
					queue.add(bridge.destination);
					isVisited[bridge.destination] = true;
				}
			}
		}

		return false;
	}

	public static void clearVisit(boolean[] isVisited) {
		Arrays.fill(isVisited, false);
	}
}

class Bridge {
	int destination;
	int size;

	public Bridge(int destination, int size) {
		this.destination = destination;
		this.size = size;
	}

	@Override
	public boolean equals(Object o) {
		Bridge bridge = (Bridge) o;
		return destination == bridge.destination;
	}

	@Override
	public int hashCode() {
		return Objects.hash(destination);
	}
}

'알고리즘 공부 > boj' 카테고리의 다른 글

boj 16637: 괄호 추가하기  (0) 2021.01.27
boj 1167: 트리의 지름  (0) 2021.01.25
boj 17143: 낚시왕  (0) 2021.01.20
boj 1005: ACM Craft  (0) 2021.01.20
boj 1949: 우수 마을  (0) 2021.01.19

시뮬레이션 문제이다. 시키는대로만 구현하면 된다.

행렬이 범위만 주의하도록 하자 1 ≤ r ≤ R, 1 ≤ c ≤ C

import java.util.*;

public class Main {
	public static int dr[] = { -1, 1, 0, 0 };
	public static int dc[] = { 0, 0, 1, -1 };

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int row = in.nextInt();
		int col = in.nextInt();
		int n = in.nextInt();
		int mat[][] = new int[row + 1][col + 1];

		Shark sharks[] = new Shark[n + 1];
		for (int i = 1; i <= n; i++) {
			int r = in.nextInt();
			int c = in.nextInt();
			int s = in.nextInt();
			int d = in.nextInt();
			int z = in.nextInt();

			sharks[i] = new Shark(i, r, c, s, dr[d - 1], dc[d - 1], z);
			mat[r][c] = i;
		}

		int sum = 0;

		for (int i = 1; i <= col; i++) {
			sum += getShark(i, mat, sharks);
			moveShark(mat, sharks, row, col);
		}
		System.out.println(sum);
	}

	public static int getShark(int col, int[][] mat, Shark[] sharks) {
		for (int i = 0; i < mat.length; i++) {
			if (mat[i][col] != 0) {

				int size = sharks[mat[i][col]].size;
				sharks[mat[i][col]] = null;
				mat[i][col] = 0;

				return size;
			}
		}
		return 0;
	}

	public static void moveShark(int[][] mat, Shark[] sharks, int maxRow, int maxCol) {
		for (int i = 1; i < sharks.length; i++) {
			Shark shark = sharks[i];

			if (shark != null) {
				mat[shark.row][shark.col] = 0;
				shark.move(maxRow, maxCol, shark.speed);
			}
		}

		for (int i = 1; i < sharks.length; i++) {
			Shark shark = sharks[i];

			if (shark != null) {
				if (mat[shark.row][shark.col] == 0) {
					mat[shark.row][shark.col] = i;
				} else {
					Shark beforeShark = sharks[mat[shark.row][shark.col]];
					if (beforeShark.size > shark.size) {
						sharks[i] = null;
					} else {
						sharks[mat[shark.row][shark.col]] = null;
						mat[shark.row][shark.col] = i;
					}
				}
			}
		}
	}
}

class Shark {
	int name;
	int row;
	int col;
	int speed;
	int dr;
	int dc;
	int size;

	public Shark(int name, int row, int col, int speed, int dr, int dc, int size) {
		this.name = name;
		this.row = row;
		this.col = col;
		this.speed = speed;
		this.dr = dr;
		this.dc = dc;
		this.size = size;
	}

	public void changeDirection() {
		this.dr = -dr;
		this.dc = -dc;
	}

	public void move(int maxRow, int maxCol, int move) {
		// 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
		if (move == 0) {
			return;
		}

		int newRow = row + dr * move;
		int newCol = col + dc * move;
		if (newRow > 0 && newCol > 0 && newRow <= maxRow && newCol <= maxCol) {
			row = newRow;
			col = newCol;
			return;
		}

		if (newRow <= 0) {
			row = 1;
			changeDirection();
			move(maxRow, maxCol, 1 - newRow);
			return;
		}
		if (newCol <= 0) {
			col = 1;
			changeDirection();
			move(maxRow, maxCol, 1 - newCol);
			return;
		}
		if (newRow > maxRow) {
			row = maxRow;
			changeDirection();
			move(maxRow, maxCol, newRow - maxRow);
			return;
		}
		if (newCol > maxCol) {
			col = maxCol;
			changeDirection();
			move(maxRow, maxCol, newCol - maxCol);
			return;
		}

	}
}

'알고리즘 공부 > boj' 카테고리의 다른 글

boj 1167: 트리의 지름  (0) 2021.01.25
boj 1939: 중량제한  (0) 2021.01.20
boj 1005: ACM Craft  (0) 2021.01.20
boj 1949: 우수 마을  (0) 2021.01.19
boj 1981: 배열에서 이동  (0) 2021.01.17

문제 조건

1. 건물을 건설하는데 순서가 존재한다.

2. 건물 건설은 동시에 가능하다

 

이 문제는 전형적인 위상정렬 문제이다.

 

아래와 같이 건물을 건설하는 데에 필요한 정보는 아래 2가지 정보이며, 예제 1에 적용해 보자

- 기다려야 하는 시간 building

- 건물을 건설하기 위해 먼저 건설해야 하는 노드의 개수 parentNum

<time=0>



 

 

 

 

 

 

 

 

 

 

 

<time=10>

 

 

parentNum[i] = 0인 노드부터 건설하면 된다. 큐에 넣어서 순차적으로 처리해 보자

빌딩을 건설해 주고 나면 i를 부모 노드로 하는 자식 노드들의 parentNum을 하나씩 줄여준다.

 

 

 

 

 

 

 

 

 

<time=110>

 

빌딩은 동시에 건설이 가능하기 때문에,

같은 depth의 노드들의 building 중 최댓값을 time에 더해주도록 한다.

 

 

 

 

 

 

 

 

 

 

 

 

마지막으로 최종 목표 destination node가 나타나면 바로 건설 시간을 더해준 후 리턴해준다.

 

 

풀이 코드는 아래와 같다.

import java.util.*;

public class Main {
	public static int max = 0;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int test = in.nextInt();
		for (int t = 0; t < test; t++) {
			int v = in.nextInt();
			int e = in.nextInt();
			int building[] = new int[v + 1];

			for (int i = 1; i <= v; i++) {
				building[i] = in.nextInt();
			}

			LinkedList<Integer> childs[] = new LinkedList[v + 1];
			LinkedList<Integer> parents[] = new LinkedList[v + 1];
			for (int i = 1; i <= v; i++) {
				childs[i] = new LinkedList<Integer>();
				parents[i] = new LinkedList<Integer>();
			}

			int[] parentNum = new int[v + 1];

			for (int i = 0; i < e; i++) {
				int parentNode = in.nextInt();
				int childNode = in.nextInt();

				childs[parentNode].add(childNode);
				parents[childNode].add(parentNode);
				parentNum[childNode]++;
			}

			int destination = in.nextInt();

			System.out.println(calculateTime(destination, building, parentNum, childs, parents));
		}
	}

	public static int calculateTime(int destination, int[] building, int[] parentNum, LinkedList<Integer> childs[],
			LinkedList<Integer> parents[]) {
		boolean[] isVisited = new boolean[building.length];

		Queue<Integer> queue = new LinkedList<Integer>();
		for (int i = 1; i < building.length; i++) {
			if (parentNum[i] == 0) {
				if (i == destination) { // 바로 건설 가능한 경우
					return building[i];
				}

				queue.add(i);
			}
		}

		while (!queue.isEmpty()) {
			int now = queue.poll();
			isVisited[now] = true;

			for (int node : childs[now]) {
				parentNum[node]--;

				if (!isVisited[node] && parentNum[node] == 0) {
					queue.add(node);

					int max = 0;
					for (int parent : parents[node]) {
						max = Math.max(max, building[parent]);
					}
					building[node] += max;

					if (node == destination) {
						return building[destination];
					}
				}
			}
		}

		return building[destination];
	}
}

조금 어려웠던 점은 아래와 같은 반례를 생각하지 못했어서 맞왜틀을 고민했었다.

올바르게 시간을 구하기 위해서는 부모 노드들 또한 저장해야해야 했는데, 다른 스터디원들에 비해 실행 시간이 너무 오래 걸려서

한 번 생각해 봐야겠다...

'알고리즘 공부 > boj' 카테고리의 다른 글

boj 1939: 중량제한  (0) 2021.01.20
boj 17143: 낚시왕  (0) 2021.01.20
boj 1949: 우수 마을  (0) 2021.01.19
boj 1981: 배열에서 이동  (0) 2021.01.17
boj 3745: 오름세  (0) 2021.01.15

문제 조건

'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

 

이 문제의 경우는 우수 마을에 포함할지 말지 모두 구한 후 조건에 맞는지 확인하는 방식으로 푼다면 O(2^N)으로 시간초과가 날 것이다.

'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다. => DP를 사용하면 될 것 같다.

 

우수마을의 경우 트리 형태이고, 이 트리에서 DP를 사용해서 문제를 풀어야 한다.

이 문제에선, 부모 노드를 우수 마을에 포함할 경우, 자식노드는 우수 마을에 포함하면 안된다.

그리고 일반 마을이 부모 노드일 경우, 자식 노드에는 우수 마을이 있어야 한다.(합을 최대로 구해야 하니까)

 

dp[i][0]: i번 마을이 우수 마을이 아니었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값
dp[i][1]: i번 마을이 우수 마을이었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값

 

 

 

아무 노드나 루트로 삼고 DFS를 진행한다. => 1로 시작하자

 

왜냐면 조건중에

나라는 트리(Tree) 구조로 이루어져 있으며, 즉 마을과 마을 사이를 직접 잇는 N-1개의 방향 없는 길이 있으며,

모든 마을은 연결되어 있다. 는 조건이 있기 때문이다.

 

이 문제에서 주어진 문제는 방향이 없는 연결을 가지는 트리이며, 모든 노드가 루트 노드가 될 수 있다.

 

DFS를 사용한 이유는 순회를 하면서 우수마을 조건에 포함하고 포함하지 않는 식의 백트래킹을 이용하기 위해서이다.

 

 

 

 

 

 

 

 

 

 

 

리프노드에 도달하게 되면,

노드 5와 같이 다시 거슬러 올라오면서 dp값을 채우도록 한다.

 

 

노드 2까지 올라오면 다른 분기점으로 내려가면서

마찬가지로 방문하지 않은 노드까지 찾아내려간다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

결론적으로 업데이트된 dp의 최종 결과는 아래와 같다.

그리고 이를 적용한 코드는 아래와 같다

import java.util.*;

public class Main {
	public static int max = 0;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int people[] = new int[n + 1];
		LinkedList<Integer> connections[] = new LinkedList[n + 1];

		for (int i = 1; i <= n; i++) {
			people[i] = in.nextInt();
			connections[i] = new LinkedList<Integer>();
		}

		for (int i = 1; i < n; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			connections[a].add(b);
			connections[b].add(a);
		}

		/*
		 * dp[i][0]: i번 마을이 우수 마을이 아니었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값,
		 * 
		 * dp[i][1]: i번 마을이 우수 마을이었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값
		 * 
		 */
		int dp[][] = new int[n + 1][2];
		boolean isVisited[] = new boolean[n + 1];
		int start = 1;
		dfs(start, isVisited, people, dp, connections);

		System.out.println(Math.max(dp[start][0], dp[start][1]));
	}

	public static void dfs(int root, boolean[] isVisited, int[] people, int[][] dp, LinkedList<Integer> connections[]) {
		isVisited[root] = true;
		for (int next : connections[root]) {
			if (!isVisited[next]) {
				dfs(next, isVisited, people, dp, connections);
			}
		}
		dp[root][0] = 0;
		dp[root][1] = people[root];
		for (int next : connections[root]) {
			dp[root][0] += Math.max(dp[next][0], dp[next][1]);
			dp[root][1] += dp[next][0];
		}
	}
}

 

주의할 점은 top down방식으로 dp를 업데이트 하게 되면 분기점 등에서 겹치는 값이 생길 수 있으므로

botton up 방식으로 값을 업데이트 하도록 해야 한다.

'알고리즘 공부 > boj' 카테고리의 다른 글

boj 17143: 낚시왕  (0) 2021.01.20
boj 1005: ACM Craft  (0) 2021.01.20
boj 1981: 배열에서 이동  (0) 2021.01.17
boj 3745: 오름세  (0) 2021.01.15
boj 1091: 카드 섞기  (0) 2021.01.11

+ Recent posts