<!doctype html>
programmers. 배달
문제를 정리하는데 좀 시간이 걸렸던 문제였습니다. 일단 이런 문제에서는 각 노드간의 연결관계를 정리하는 자료구조가 필요합니다. 그 자료 구조에는 다음과 같은 내용이 담겨야 합니다.
- 각 노드는 다른 어떤 노드와 연결이 되어있는가?
- 각 다른 노드와의 연결시 가중치가 얼마나 되는가?
보통은 위와 같은 조건에서 끝나지만 이 문제에서 다른 점이 있다면 각 노드를 선의 중복이 있을 수 있다는 것입니다. 물론 문제에서 구하고자 하는 것이 가장 많은 마을을 돌아야 하니까 중복이 있더라도 가중치 작은걸로 초반에 걸러주면 될겁니다.
이 연결관계만 정리되어 있다면 순회를 해야하는데 저는 dfs로 풀었습니다. dfs가 적절하다고 생각했던 이유는 한번 시행시 끝을 보는 것이 문제 푸는데 단순하다고 생각했기 때문입니다. 끝을 본다는 건 재귀를 통해 갈 수 있는 최대까지 간다는 것을 의미합니다. bfs는 주위 연결된 것을 하나하나씩 해본다는 점에서 다르죠.
connections에 해당 노드와 연결되는 To에 대한 List로 Map 을 만들었습니다. 밑에 History는 이 connections에 대한 데이터를 정리하는데 사용되었습니다. connections 을 구성하고 막상 dfs로 풀려고 하니까 제가 왜 이렇게 복잡하게 풀었는가 생각이 들더라구요. 이 자료구조를 좀 더 단순하면서 효율적으로 만드는 것이 제가 이 문제를 통해 해결해야 할 과제같습니다.
checkVisited() 로 인해 마지막 테스트 케이스에서 '시간 초과'가 발생했는데 이후에 생각해보니 굳이 for문 한 번 더 돌면서 체크 할 필요가 없겠더라구요. 그냥 visitedHistory 에 체크하고 나서 안 돌려놓으면 되는 것이죠!! 비트마스크도 생각했는데 Int가 18자리까지이고 이후로는 안되어 이건 아니겠다는 생각이 들었습니다(다행.. ㅋㅋ)
class Solution {
private Map<Integer, List<To>> connections = new HashMap<>();
private boolean[] visited; // 1base
private boolean[] visitedHistory; // 1base
private int answer = 0;
private int K;
public int solution(int N, int[][] road, int K) {
visited = new boolean[N + 1];
visitedHistory = new boolean[N + 1];
this.K = K;
createConnections(road);
visited[1] = true;
visitedHistory[1] = true;
dfs(1, 0);
for (boolean b : visitedHistory) {
if(b) answer++;
}
return answer;
}
public void dfs(int from, int sum) {
List<To> tos = connections.get(from);
for (To toData : tos) {
int to = toData.getTo();
if (visited[to] || sum + toData.getEffort() > K) {
// answer = Math.max(answer, checkVisited());
continue;
}
visited[to] = true;
visitedHistory[to] = true;
dfs(to, sum + toData.getEffort());
visited[to] = false;
}
}
// checkVisited 이 N^2을 만들어 느릴 수 있다. 비트마스크로 바꿔보자!
public int checkVisited() {
int res = 0;
for (int i = 0; i < visited.length; i++) {
if (visited[i]) visitedHistory[i] = true;
if (visitedHistory[i]) res++;
}
return res;
}
private void createConnections(int[][] road) {
Map<String, Integer> data = new HashMap<>();
for (int[] ints : road) {
int from = ints[0];
int to = ints[1];
int val = ints[2];
String history = History.printHistory(from, to);
int v = data.getOrDefault(history, Integer.MAX_VALUE);
data.put(history, Math.min(val, v));
}
for (String s : data.keySet()) {
int from = History.extractFrom(s);
int to = History.extractTo(s);
int val = data.get(s);
List<To> tos = connections.getOrDefault(from, new ArrayList<>());
List<To> froms = connections.getOrDefault(to, new ArrayList<>());
tos.add(new To(to, val));
froms.add(new To(from, val));
connections.put(from, tos);
connections.put(to, froms);
}
}
static class To {
private final int to;
private final int effort;
public To(int to, int effort) {
this.to = to;
this.effort = effort;
}
public int getTo() {
return to;
}
public int getEffort() {
return effort;
}
@Override
public String toString() {
return "{to=" + to + ", effort=" + effort + '}';
}
}
static class History {
private static final String historyFormat = "(%d,%d)";
private Set<String> history;
public History() {
this.history = new HashSet<>();
}
public void saveHistory(int from, int to) {
history.add(printHistory(from, to));
}
public void removeHistory(int from, int to) {
history.remove(printHistory(from, to));
}
public boolean hasHistory(int from, int to) {
return history.contains(printHistory(from, to));
}
public static int extractFrom(String history) {
String sub = history.substring(1, history.length() - 1);
return Integer.parseInt(sub.split(",")[0]);
}
public static int extractTo(String history) {
String sub = history.substring(1, history.length() - 1);
return Integer.parseInt(sub.split(",")[1]);
}
public static String printHistory(int from, int to) {
return String.format(historyFormat, from, to);
}
}
}
'Algorithm > problem solving' 카테고리의 다른 글
| leecode 253. Meeting Rooms II (0) | 2023.03.20 |
|---|---|
| leetcode 2102. Sequentially Ordinal Rank Tracker (0) | 2023.03.19 |
| Today's Algorithm(2019-03-20) (2) | 2019.03.20 |
| Today's Algorithm(2019-03-18) (0) | 2019.03.18 |
| Today's Algorithm(2019-03-17) (0) | 2019.03.17 |
