주의해야 할 점은 A + B + C의 경우에는 앞에 있는 +가 우선순위가 더 높기 때문에 ABC++가 아닌 (A + B) + C로 묶어서 AB+C+가 나와야 합니다.
그리고 추가로 괄호로 묶여서 제공되는 연산자의 경우에는 가장 우선순위가 높기 때문에 가장 먼저 처리해줘야 합니다.
알파벳에 해당하는 (A ~ Z)는 바로 문자열에 추가하고, 연산자(+, -, *, /)는 Stack에 저장해야 합니다.
2. 핵심 아이디어
Stack에는 연산자 들이 저장됩니다. 즉 먼저 들어온 연산자들은 아래쪽에 쌓이게 됩니다.
첫 번째 아이디어는 "("가 스택에 들어왔을 때입니다.
"("는 일단 스택에 넣어줍니다. 그다음 연산자를 받아주고, 닫는 괄호 ")"가 들어왔을 때, 괄호 내부에 있는 연산자를 뽑아주는 작업을 해야 합니다.
그 이유는 괄호 안에 있는 연산자가 어떤 연산자인지 상관없이 우선순위가 높기 때문입니다.
이때는 while에 조건을 넣어서 "("가 나올 때까지 pop을 해서 뽑아내서 정답 문자열 뒤에 붙여줍니다. 이때 "("는 정답에 포함되면 안 됩니다.
두 번째 아이디어는 이전에 스택에 들어온 연산자 중에서 나보다 우선순위가 높은 연산자가 있는지 확인해서 추출해야 합니다.
후위 표기식에서는 알파벳 뒤에는 우선순위가 높은 순서로 연산자가 붙습니다.
A + B * C 라면 우선순위가 높은 순서로 ABC*+ 이렇게 붙게 됩니다.
그래서 이미 스택에 들어온 연산자들 중에서 내가 현재 가지고 있는 연산자 보다 높은 우선순위가 존재하면 안 됩니다.
세 번째 아이디어는 수식의 모든 순회를 끝냈을 때, Stack에 남아있는 연산자들을 순서대로 추출해서 정답 문자열에 더해줘야 합니다.
3. 코드 작성
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String notation = br.readLine();
Stack<Character> operator = new Stack<>();
StringBuilder builder = new StringBuilder();
for (int i = 0; i < notation.length(); i++) {
char value = notation.charAt(i);
if (value >= 'A' && value <= 'Z') {
builder.append(value);
} else if (value == '(') {
operator.add(value);
} else if (value == ')') {
// 닫는 괄호가 나오면 여는 괄호가 나올 때까지 빼서 연산자만 추출한다. (괄호안에 연산자가 우선순위가 있기 떄문에)
while (!operator.isEmpty()) {
char popVal = operator.pop();
if (popVal == '(') {
break;
}
builder.append(popVal);
}
} else {
// 괄호가 아닌 경우에는 이전 연산자가 현재 연산자보다 우선순위가 높은지 확인 후 추출
while (!operator.isEmpty() && checkPriority(operator.peek(), value)) {
builder.append(operator.pop());
}
operator.add(value);
}
}
// 남아있을 수 있는 부분이 있어서 나머지 모두 추출해서 뒤에 붙여줌
while (!operator.isEmpty()) {
builder.append(operator.pop());
}
System.out.println(builder);
}
public static boolean checkPriority(char peekVal, char val) {
int peekValWeight = setWeight(peekVal);
int valWeight = setWeight(val);
// 같은 순위의 연산자라면 먼저 나온 것이 우선순위가 크기 때문에 등호가 필수
return peekValWeight >= valWeight;
}
public static int setWeight(char val) {
if (val == '(') return 0;
return val == '+' || val == '-' ? 1 : 2;
}
}
이동은 상, 하, 좌, 우로 가능하고, 이때 벽(1)을 최소 한번 부수고 지나갈 수 있습니다.
문제에서 주어진 사항을 보고, BFS로 접근해야겠다는 생각을 했습니다.
방향이 존재하기 때문에 재귀적으로 구현을 했고, 벽을 1번 이상 부순 경우는 더 이상 나아가지 못하도록 막는 방법을 생각했습니다.
계속 틀렸다는 말이 나와서 2차원 배열 visited를 이용하여 문제를 변경해서 풀어봤는데, 이때는 시간 초과가 났습니다.
2. 핵심 아이디어
특정한 지점 (x, y)에 도달하는 데 있어서 벽을 1번 부수고 가는 경우와 벽을 아예 부수지 않고 가는 경우 중에서 벽을 1번 부수고 가는 경우가 더 빠를 수 있습니다.
특정 지점 (x, y)까지의 결과는 위와 같지만, 최종 (N, M)까지 도달하는 데 있어서는 벽을 아예 부수지 않고 가는 경우가 더 빠를 수 있습니다.
위 그림 처럼 파란 지점까지 벽을 한 번 부수고 가면 3번이면 가는데, 벽을 부수지 않고 가면 13번이 걸립니다.
하지만 벽을 한번 부수고 3번으로 지나가면 (N, M)에 도달하지 못하고 정답이 될 수 없습니다.
파란 지점에 벽을 한번 부순것이 먼저 도달해서 visited[1][3]을 true로 만들었고, 벽을 부수지 않고 지나가는 경우에 같은 vistied를 사용하게 된다면 해당 경우는 도달할 수 있는 경우가 -1이 됩니다.
즉, 벽을 부수고 지나가는 경우에 대한 visited와 벽을 부수지 않고 지나가는 경우에 대한 visited를 나눠서 처리해줘야 합니다.
이 문제에서 2차원 배열을 2개 만드는 것 보다 visited[][][]를 3차원 배열로 만들어서 visited[row][col][0]은 벽을 부수고 지나가는 경우에 대한 visited로 사용하고, visited[row][col][1]은 벽을 부수지 않고 지나가는 경우에 대한 visited로 사용하면 쉽게 처리할 수 있습니다.
3. 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] map;
static boolean[][][] visited;
static int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N + 1][M + 1];
visited = new boolean[N + 1][M + 1][2]; // (벽을 부수고 가는 경우, 벽을 부수지 않고 가는 경우)
for (int row = 1; row <= N; row++) {
char[] input = br.readLine().toCharArray();
for (int col = 1; col <= M; col++) {
map[row][col] = input[col - 1] - '0';
}
}
int answer = bfs();
System.out.println(answer);
}
public static int bfs() {
Queue<Node> nodes = new LinkedList<>();
nodes.add(new Node(1, 1, 1, false));
visited[1][1][1] = true;
while (!nodes.isEmpty()) {
Node curr = nodes.poll();
if (curr.row == N && curr.col == M) {
return curr.dist;
}
int nextDist = curr.dist + 1;
for (int[] m : move) {
int nextRow = curr.row + m[0];
int nextCol = curr.col + m[1];
if (!isValid(nextRow, nextCol)) {
continue;
}
if (map[nextRow][nextCol] == 1) { // 벽인 경우
if (!curr.useBreak && !visited[nextRow][nextCol][0]) { // 아직 부순적이 없는 경우
nodes.add(new Node(nextRow, nextCol, nextDist, true));
visited[nextRow][nextCol][0] = true;
}
} else if (map[nextRow][nextCol] == 0) { // 벽이 아닌 경우
if (curr.useBreak && !visited[nextRow][nextCol][0]) { // 벽을 부수고 가는 경우
nodes.add(new Node(nextRow, nextCol, nextDist, true));
visited[nextRow][nextCol][0] = true;
} else if (!curr.useBreak && !visited[nextRow][nextCol][1]) { // 벽을 부수지 않고 가는 경우
nodes.add(new Node(nextRow, nextCol, nextDist, false));
visited[nextRow][nextCol][1] = true;
}
}
}
}
return -1;
}
public static boolean isValid(int row, int col) {
return row >= 1 && col >= 1 && row <= N && col <= M;
}
static class Node {
int row, col, dist;
boolean useBreak;
public Node (int row, int col, int dist, boolean useBreak) {
this.row = row;
this.col = col;
this.dist = dist;
this.useBreak = useBreak;
}
}
}
특정 노드 2개를 선택해서 쭉 늘렸을 때, 가장 길이가 긴 두 노드를 찾아야 한다. 이 길이를 문제에서는 트리의 지름이라고 칭합니다.
1번 노드부터 탐색해서 가장 가중치가 큰 노드 하나를 선택합니다.
가장 가중치가 큰 노드는 반드시 트리의 지름의 한 점이 된다고 생각했습니다.
가장 가중치가 큰 노드를 하나 선택했으면, 해당 노드부터 BFS로 다시 탐색을 시작해서 가장 길이가 긴 값(트리의 지름)을 반환합니다.
2. 접근 과정에서 실수했던 부분
문제에서 "간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다."라는 부분이 있었습니다.
이 부분을 잘못 이해해서 다음과 같이 문제 접근을 시작했습니다.
(1) 입력을 받으면서 가장 가중치가 큰 노드를 선택
Node[] nodes = new Node[n + 1]; // 가장 가중치가 큰 노드를 찾기 위한 배열
nodes[0] = new Node(0, 0); // NullPointerException 방지를 위해
nodes[1] = new Node(1, 0); // 1번은 루트이기 때문에 가중치가 0
for (int i = 1; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
map[first].add(new Node(second, weight)); // 트리의 양방향 설정
map[second].add(new Node(first, weight)); // 트리의 양방향 설정
int beforeWeight = nodes[first] == null ? 0 : nodes[first].weight;
nodes[second] = new Node(second, beforeWeight + weight);
}
Arrays.sort(nodes, (n1, n2) -> n2.weight - n1.weight);
// 도달 거리가 가장 큰 놈을 하나 선택
int start = nodes[0].end;
O(N)에 모든 것을 다 챙겨가려는 오만한 생각에 코드를 이렇게 짰습니다.
이렇게 해서 문제 제출을 해보니 67%쯤에서 계속 틀렸다고 나왔습니다.
(2) 도움이 됐던 반례
이진 트리라는 조건이 없어서 생겼던 웬만한 반례들은 모두 통과가 됐습니다.
그래서 처음에는 어느 부분에서 실수를 한지 판단할 수가 없어서 계속 생각해 보다가 알고리즘에 도움을 줬던 반례가 있었습니다.
"간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다."라는 조건은 확실하게 만족하는 입력 값들이었습니다.
제 알고리즘대로라면 {2 5 1}이 입력되었을 때, 5라는 노드의 가중치는 2라는 노드의 가중치에 1을 더한 값이 세팅되어야 합니다. 하지만 위 입력에서는 아직 노드 2에 대한 제대로 된 가중치가 저장되기 전이기 때문에 옳지 않은 정답을 출력한 것을 알 수 있습니다.
3. 문제 해결
기존의 나머지 알고리즘은 그대로 두고, 문제가 있던 입력받는 부분에 대해서만 수정을 했습니다.
입력은 그대로 인접 리스트를 사용하여 양방향 정보를 저장하고, BFS 탐색을 2번 했습니다.
첫 번째 탐색에서는 가중치의 최대값을 갱신하면서 그 최대 가중치를 갖는 노드(start)를 찾아냈습니다.
두 번째 탐색에서는 최대 가중치를 갖는 노드(start)부터 다시 탐색을 시작해서 가장 가중치가 긴 값(트리의 지름)을 갱신해서 반환했습니다.
import java.io.*;
import java.util.*;
public class Main {
static int n, start;
static List<Node>[] map;
static boolean[] visited;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/main.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
map[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
map[first].add(new Node(second, weight));
map[second].add(new Node(first, weight));
}
// 가장 큰 노드를 탐색
visited = new boolean[n + 1];
bfs(1);
// 해당 노드부터 탐색을 시작해서 최장 거리를 찾음
visited = new boolean[n + 1];
int result = bfs(start);
System.out.println(result);
}
public static int bfs(int startNodeNumber) {
int result = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(startNodeNumber, 0));
visited[startNodeNumber] = true;
while (!queue.isEmpty()) {
Node curr = queue.poll();
if (result < curr.weight) {
result = curr.weight;
start = curr.end;
}
for (Node node : map[curr.end]) {
if (visited[node.end]) continue;
queue.add(new Node(node.end, curr.weight + node.weight));
visited[node.end] = true;
}
}
return result;
}
static class Node {
int end;
int weight;
public Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
}
플로이드 와샬 알고리즘은 O(N^3)의 시간 복잡도가 필요하다. 마을의 개수(N)가 최대 10^3이기 때문에 플로이드 와샬을 사용하면 최대 10^9의 시간이 걸릴 수 있어 시간 초과가 날 가능성이 있다.
그럼 고려해 볼 수 있는 알고리즘은 다익스트라 알고리즘이다.
다음은 각 마을에서 X로 가는 최단 거리와, X에서 다시 각 마을로 돌아가는 최단 거리를 구해야 한다.
그대로 구현한다면 1, 3, 4 마을에서 각각 2번 마을까지 갈 수 있는 거리를 구해야 한다. 이를 반대로 생각해 보면 다음과 같이 접근해 볼 수 있다.
(시작 마을) (끝 마을) (거리)를 입력받을 때, 입력받은 대로 저장하는 경우 map과 (끝 마을) (시작 마을) (거리)로 저장하는 경우reverseMap을 모두 저장한다.
X 마을에서 각 마을(1, 3, 4)로 돌아가는 경우를 구할 때는 map을 사용하면 X 마을을 시작점으로 각 마을로 돌아가는 거리를 구할 수 있다.
각 마을(1, 3, 4)에서 X 마을로 가는 경우를 구할 때는 reverseMap을 사용하면 X 마을을 시작점으로 각 마을로 가는 거리를 구할 수 있다.
이렇게 reverseMap을 사용하면 X 마을이 도착점이 아닌 시작 마을로 해서 간단하게 다익스트라 알고리즘을 2번 돌려주면 원하는 값을 얻을 수 있다.
3. 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, X;
static List<Node>[] map, reverseMap; // 인접 리스트로 저장
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
map = new ArrayList[N + 1];
reverseMap = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
map[i] = new ArrayList<>();
reverseMap[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int dist = Integer.parseInt(st.nextToken());
map[start].add(new Node(end, dist));
reverseMap[end].add(new Node(start, dist));
}
int[] go = dijkstra(reverseMap); // 각 노드에서 X로 가는 최단 경로
int[] back = dijkstra(map); // X에서 각 노드로 가는 최단 경로
int answer = 0;
for (int i = 1; i <= N; i++) {
answer = Math.max(answer, go[i] + back[i]);
}
System.out.println(answer);
}
public static int[] dijkstra(List<Node>[] inputMap) {
boolean[] visited = new boolean[N + 1];
int[] result = new int[N + 1];
Arrays.fill(result, Integer.MAX_VALUE);
result[X] = 0; // X에서 X로 가는 경로는 0으로 초기화
// 다익스트라 알고리즘 시작
PriorityQueue<Node> queue = new PriorityQueue<>((n1, n2) -> n1.dist - n2.dist);
queue.add(new Node(X, 0));
while (!queue.isEmpty()) {
Node curr = queue.poll();
if (visited[curr.end]) {
continue;
}
visited[curr.end] = true;
for (Node node : inputMap[curr.end]) {
if (curr.dist + node.dist < result[node.end]) {
result[node.end] = curr.dist + node.dist;
}
queue.add(new Node(node.end, result[node.end]));
}
}
return result;
}
static class Node {
int end, dist;
public Node (int end, int dist) {
this.end = end;
this.dist = dist;
}
}
}
저는 다익스트라 알고리즘에 사용될 map과 reverseMap을 인접리스트 형식으로 저장했습니다.
PriorityQueue를 사용해서 Node의 dist(거리)를 기준으로 오름차순 정렬되도록 선언했습니다.
거리 기준 오름차순으로 저장하면 해당 노드로 도달할 수 있는 최단 거리를 얻을 수 있고, 같은 노드에 대한 정보가 나중에 들어오면 visited를 통해서 contitnue로 걸러줬습니다.
4. 알게 된 점
그래프에서 어떤 특정 노드까지 이동을 하고, 다시 되돌아와야 하는 경우가 존재한다면, 해당 특정 노드를 시작점으로 해결해 볼 수 있다는 것을 알게 되었습니다. (입력을 거꾸로 저장, reverseMap)
