인프런 커뮤니티 질문&답변
작성한 질문수
백준 1325 질문있습니다!
해결된 질문
작성
·
819
1
안녕하세요! 강의를 다 듣고, 블로그에 남겨주신 문제들을 풀어보고 있습니다.
'백준 1325 효율적인 해킹 문제'인데, 시간 초과가 나는 기준을 이해하지 못해서 질문드립니다!
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static int N, M;
private static List<List<Integer>> graph;
private static boolean[] visited;
private static int dfs(int idx) {
visited[idx] = true;
int count = 1;
for (int next : graph.get(idx)) {
if (!visited[next]) {
count += dfs(next);
}
}
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new ArrayList<>(N + 1);
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph.get(b).add(a);
}
int max = -1;
List<Integer> answer = new ArrayList<>();
for (int i = 1; i <= N; i++) {
visited = new boolean[N + 1];
int count = dfs(i);
if (max < count) {
answer.clear();
answer.add(i);
max = count;
} else if (max == count) {
answer.add(i);
}
}
Collections.sort(answer);
StringBuilder sb = new StringBuilder();
for (int n : answer) {
sb.append(n);
sb.append(" ");
}
bw.write(sb.toString());
br.close();
bw.close();
}
}
이렇게 작성을 하니 자꾸 시간 초과가 나와서 chat gpt에 질문해보니 메모이제이션을 사용하면 해결할 수 있다는 답변이 나왔습니다.
이미 visited를 사용해 이미 방문한 노드를 다시 방문하지 않는데, 메모이제이션을 사용하는게 의미가 있을까 싶었지만 일단 코드를 변경해봤습니다.
import java.io.*;
import java.util.*;
public class Main {
private static int N, M;
private static List<List<Integer>> graph;
private static boolean[] visited;
private static int[] memo;
private static int dfs(int idx) {
if (memo[idx] != -1) {
return memo[idx];
}
visited[idx] = true;
int count = 1;
for (int next : graph.get(idx)) {
if (!visited[next]) {
count += dfs(next);
}
}
memo[idx] = count;
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new ArrayList<>(N + 1);
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph.get(b).add(a);
}
int max = -1;
List<Integer> answer = new ArrayList<>();
for (int i = 1; i <= N; i++) {
visited = new boolean[N + 1];
memo = new int[N + 1];
Arrays.fill(memo, -1);
int count = dfs(i);
if (max < count) {
answer.clear();
answer.add(i);
max = count;
} else if (max == count) {
answer.add(i);
}
}
Collections.sort(answer);
StringBuilder sb = new StringBuilder();
for (int n : answer) {
sb.append(n);
sb.append(" ");
}
bw.write(sb.toString());
br.close();
bw.close();
}
}
이렇게 작성하니까 시간 초과가 나지는 않는데, 어느 테스트 케이스에서 memo 배열에 저장된 값을 사용하는건지 알 수 있을까요?
그리고 혹시 강사님은 이 문제를 이것과 다르게 푸셨을까요??
++ 추가로 배열 대신 HashMap을 사용해도 시간 초과가 납니다... ㅠ
import java.io.*;
import java.util.*;
public class Main {
private static int N, M;
private static List<List<Integer>> graph;
private static boolean[] visited;
private static Map<Integer, Integer> map;
private static int dfs(int idx) {
if (map.get(idx) != null) {
return map.get(idx);
}
visited[idx] = true;
int count = 1;
for (int next : graph.get(idx)) {
if (!visited[next]) {
count += dfs(next);
}
}
map.put(idx, count);
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new ArrayList<>(N + 1);
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph.get(b).add(a);
}
int max = -1;
List<Integer> answer = new ArrayList<>();
for (int i = 1; i <= N; i++) {
visited = new boolean[N + 1];
map = new HashMap<>();
int count = dfs(i);
if (max < count) {
answer.clear();
answer.add(i);
max = count;
} else if (max == count) {
answer.add(i);
}
}
Collections.sort(answer);
StringBuilder sb = new StringBuilder();
for (int n : answer) {
sb.append(n);
sb.append(" ");
}
bw.write(sb.toString());
br.close();
bw.close();
}
}
답변 1
2
안녕하세요 :)
벌써 추가 문제들까지 풀고 계시다니! 너무 잘하고 계셔서 제가 다 뿌듯하네요 :)
빨리 답변 드리려고 했다가 다른 분들은 어떻게 풀었는지 참고하다 약간 늦어진 점 죄송합니다. 제 생각에 크게 3가지 해결책이 있는 것 같은데, 쉬운 순서로 설명해볼게요.
BFS로 풀기 : 가장 쉬운 방법은 BFS를 쓰는 방법일 것 같아요! 그래프 탐색이라는 측면에서는 같은 개념인데, 최악의 경우에 소요되는 시간 차이가 꽤 큽니다. 그래서 DFS로 풀 수 있는 문제는 BFS로도 풀 수 있지만, 가끔 BFS로 풀 수 있는 문제는 DFS로는 시간 초과가 발생하는 경우가 있어요. 그래서 개념적으로 가장 쉬운 방법은 BFS 알고리즘을 사용하는 겁니다.
DFS + 메모이제이션 : 만약 DFS를 꼭 사용하고 싶으시다면 메모이제이션이 함께 들어가서 계산하는 경우의 수를 많이 줄여야만 합니다. 이건 시간 복잡도를 계산해서 메모이제이션이 필요하다/필요하지 않다를 판단할 수 있으면 제일 좋지만, 만약 그렇지 못하다면 DFS로 단순하게 구현해 본 뒤 시간 초과가 발생하면 메모이제이션을 곁들여도(?) 좋은 전략이에요. 실버 상위 등급/골드 등급부터는 성능 최적화가 종종 요구되기 때문에 메모이제이션을 조금씩 익혀도 좋을 것 같아요.
DFS + 기타 최적화 : 메모이제이션이 가장 전형적인 최적화 기술이라면, 그 외에도 최적화를 하는 기술은 문제마다 다른데 이런 풀이들을 참고해보는 것도 좋은 공부가 될 수 있을 것 같아요. 물론 메모이제이션을 알면 대부분의 문제를 풀 수 있어서 2번 풀이를 익히는 게 코테를 합격할 확률을 효율적으로 올리겠지만, "이렇게도 문제를 푸는 구나"라고 한번씩 참고해보시면 시험장에서 풀이가 떠오르지 않을 때 이런 저런 최적화를 하다가 합격하게 될 수도 있어서 좋아요. (https://mygumi.tistory.com/337, 제 풀이는 아니고 전혀 모르는 분의 풀이이니 참고해주세요!)
감사합니다 ! ㅎㅎ