이분탐색으로 중량을 정해두고 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);
}
}
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;
}
}
}
아래와 같이 건물을 건설하는 데에 필요한 정보는 아래 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];
}
}
조금 어려웠던 점은 아래와 같은 반례를 생각하지 못했어서 맞왜틀을 고민했었다.
올바르게 시간을 구하기 위해서는 부모 노드들 또한 저장해야해야 했는데, 다른 스터디원들에 비해 실행 시간이 너무 오래 걸려서
'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다. 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를 업데이트 하게 되면 분기점 등에서 겹치는 값이 생길 수 있으므로
방을 방문하기 위한 순서가 있다. 2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다. 2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다. 2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다. 2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다. => 사이클이 없다
문제 조건을 읽으니 가장 먼저 위상 정렬을 이용해서 풀어야겠다는 생각이 들었다.
풀이 로직은 아래와 같다.
1. path를 이용하여 양방향 그래프를 생성한다.
2. 양방향 그래프를 bfs를 이용하여 방향 그래프로 바꾸어 준다.
3. 그래프에 order을 적용하여 위상 정렬 알고리즘을 돌린다.
class Solution {
public static boolean solution(int n, int[][] path, int[][] order) {
List<Integer>[] childs = new ArrayList[n];
for (int i = 0; i < n; i++) {
childs[i] = new ArrayList<>();
}
for (int i = 0; i < path.length; i++) {
childs[path[i][0]].add(path[i][1]);
childs[path[i][1]].add(path[i][0]);
}
return isPossible(createGraph(childs), order);
}
public static List<Integer>[] createGraph(List<Integer>[] graph) {
Queue<Integer> q = new LinkedList<>();
List<Integer>[] directedGraph = new ArrayList[graph.length];
for (int i = 0; i < directedGraph.length; i++)
directedGraph[i] = new ArrayList<>();
boolean[] v = new boolean[directedGraph.length];
q.offer(0);
v[0] = true;
while (!q.isEmpty()) {
int cur = q.poll();
for (int i = 0; i < graph[cur].size(); i++) {
int next = graph[cur].get(i);
if (v[next])
continue;
directedGraph[cur].add(next);
v[next] = true;
q.offer(next);
}
}
return directedGraph;
}
public static boolean isPossible(List<Integer>[] childs, int[][] order) {
Queue<Integer> queue = new LinkedList<>();
int[] parentNum = new int[childs.length];
for (int i = 0; i < childs.length; i++) {
for (Integer next : childs[i]) {
parentNum[next]++;
}
}
for (int i = 0; i < order.length; i++) {
childs[order[i][0]].add(order[i][1]);
parentNum[order[i][1]]++;
}
for (int i = 0; i < childs.length; i++) {
if (parentNum[i] == 0) {
queue.add(i);
}
}
int cnt = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
cnt++;
for (int i = 0; i < childs[cur].size(); i++) {
int next = childs[cur].get(i);
parentNum[next]--;
if (parentNum[next] == 0) {
queue.add(next);
}
}
}
return cnt == childs.length ? true : false;
}
}
방법 1 - 부모 노드에 대한 링크가 있는 경우 => 최대 높이가 d일 때, 공통 조상을 찾는데까지 시간 복잡도 O(d)
1. v1, v2를 루트 노드에서 거리를 구한다.
2. v1, v2를 같은 높이가 될 때까지 한 노드의 높이를 올려준다.
3. v1, v2의 높이를 하나씩 올리면서 겹치는 경우를 찾는다.
class Solution {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int test = in.nextInt();
for (int t = 1; t <= test; t++) {
int n = in.nextInt();
int e = in.nextInt();
int v1 = in.nextInt();
int v2 = in.nextInt();
LinkedList<Integer> childs[] = new LinkedList[n + 1];
for (int i = 1; i <= n; i++) {
childs[i] = new LinkedList<Integer>();
}
int[] parent = new int[n + 1];
for (int i = 0; i < e; i++) {
int p = in.nextInt();
int c = in.nextInt();
childs[p].add(c);
parent[c] = p;
}
int height1 = heightFromRootNode(v1, childs);
int height2 = heightFromRootNode(v2, childs);
int commonNode = findCommonParent(v1, v2, height1, height2, parent);
int subNodes = calculateSubNodes(commonNode, childs);
System.out.println("#" + t + " " + commonNode + " " + subNodes);
}
}
private static int calculateSubNodes(int name, LinkedList<Integer>[] childs) {
int answer = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(name);
while (!queue.isEmpty()) {
int now = queue.poll();
answer++;
queue.addAll(childs[now]);
}
return answer;
}
private static int findCommonParent(int v1, int v2, int height1, int height2, int parent[]) {
// 무조건 height1 <= height2라고 생각 -> v2를 위로 땡긴다.
if (height1 > height2) {
return findCommonParent(v2, v1, height2, height1, parent);
}
while (height1 != height2) {
v2 = parent[v2];
height2--;
}
while (v1 != v2) {
v1 = parent[v1];
v2 = parent[v2];
}
return v1;
}
private static int heightFromRootNode(int name, LinkedList<Integer>[] childs) {
int height = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1);
while (!queue.isEmpty()) {
int size = queue.size();
height++;
for (int i = 0; i < size; i++) {
int parent = queue.poll();
if (parent == name) {
return height;
}
queue.addAll(childs[parent]);
}
}
return height;
}
}
