https://www.acmicpc.net/problem/15591
문제 이해
문제를 꼼꼼히 읽어야겠다는 생각을 다시 한번 하게 된 문제입니다. 일단 주어진 문제의 레벨은 골드 5였기 때문에 그렇게 겁먹지 않고 접근을 했지만 결국 다른 풀이를 보고 나서야 풀어낼 수 있었던 문제입니다.
모든 지점에서의 모든 유사도를 이차원 int 배열에 표시를 해두고, Q를 통해서 주어진 위치에서 k 이상의 유사도를 세어보자라고 풀이를 시작했습니다. 결론적으로 해당 풀이는 기가 막힌 시간 초과를 뱉어내었습니다. 저는 이 풀이를 진행할 때에는 결국 모든 유사도를 다 구하기 때문에 DFS, BFS 관계가 없겠구나 생각을 하여 DFS를 이용해 진행했습니다.
일단 시간 초과가 나타났기 때문에 생각할 수 있는 최적화를 진행했습니다. arr[a][b]의 유사도는 곧 arr [b][a]의 유사도이므로 이도 표시 해주고, 유사도가 정해진 위치의 개수를 세어줘야 하나 같이 요런 저런 생각을 해보고 시도해 보았지만 모두 다를 바 없는 시간초과였습니다.
해당 문제에 시간을 많이 쓰고 있어서 결국 풀이를 찾아봤는데, 조금은 이해가 가지 않는 설명이었지만, 천천히 곱씹어보니 확실히 시간을 줄일 수 있는 풀이였습니다. 해당 풀이는 코드를 통해서 설명하겠습니다.
package com.baekjoon.gold;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main_BJ_15591_G1_MooTube {
static int N, Q, k; //문제에서 주어지는 N과 Q, 그리고 사용할 k
static HashMap<Integer, ArrayList<Integer>> map; //key 위치에 직접 연결 된 value 위치들
static int[][] arr; //이차원 배열을 이용해 표현한 해당 i, j 사이의 유사도
//디버깅을 하기 위해 만든 Print() 함수
static void Print(){
StringBuilder sb = new StringBuilder();
for (int i = 1; i < N+1; i++) {
for (int j = 1; j < N+1; j++) {
sb.append(arr[i][j] + " ");
}
sb.append("\n");
}
System.out.println(sb.toString().trim());
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//주어진 데이터를 입력 받아 줍니다.
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
arr = new int[N+1][N+1];
map = new HashMap<>();
//N-1 라인 만큼 입력을 받아 arr에 유사도를 표시해줍니다.
//유사도는 단방향이 아니기 때문에 양쪽으로 표시해 주었습니다.
for (int i = 0; i < N-1; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
arr[s][e] = v;
arr[e][s] = v;
//직접 연결된 두 좌표에 대해서는 주어진 유사도보다 작은 유사도가 주어질 수 없기에
//빠르게 판단하기 위해 map에 담아줍니다.
if(!map.containsKey(s)){
map.put(s, new ArrayList<>());
map.get(s).add(e);
} else {
map.get(s).add(e);
}
if(!map.containsKey(e)){
map.put(e, new ArrayList<>());
map.get(e).add(s);
} else {
map.get(e).add(s);
}
}
StringBuilder sb = new StringBuilder();
//이제 문제 Q를 직접 받아들이며 개수를 세어줄겁니다.
for (int i = 0; i < Q; i++) {
//문제에서 주어지는 k와 기준 영상 p!
st = new StringTokenizer(br.readLine());
k = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
//bfs에 사용될 q를 선언해주고, 시작점이 될 영상 p를 입력해줍니다.
Queue<Integer> q = new LinkedList<>();
q.add(p);
//유사도가 k이상이라면 개수에 포함되어야 함, 그 개수를 세어줄 cnt 입니다.
int cnt = 0;
//양방향 관계이기에 무한루프가 돌 수 있으니까 방문처리를 해주어 반복을 멈춰줄
//visited 입니다.
boolean[] visited = new boolean[N+1];
//bfs 진행!
while(!q.isEmpty()){
//q에서 좌표 하나를 꺼내줍니다!
int now = q.poll();
visited[now] = true; //방문처리!
if(now != p) cnt++; //시작할 때는 본인의 위치이나 얘는 cnt에 들어가지 않음 그 외에는 cnt++;
//현재 위치(영상)에서 갈 수 있는 곳들의 리스트를 가져옵니다!
ArrayList<Integer> nowArr = map.get(now);
//현재 영상과 연결되어 있는 좌표를 꺼내주고
//현재 영상과 다음 영상의 유사도가 k보다 클 때만! q에 담아줍니다.
//k보다 작다면 이를 통해서 연결된 모든 영상들은 k유사도 미만의 값을 가지기 때문에 어차피
//cnt에 포함될 수 없기에 담을 필요가 없습니다!!
for (int j = 0; j < nowArr.size(); j++) {
int nowEnd = nowArr.get(j);
if(arr[now][nowEnd] >= k && !visited[nowEnd]) q.add(nowEnd);
}
}
//위를 통해서 세어진 cnt를 sb에 추가해줍니다.
sb.append(cnt+"\n");
}
//sb 출력을 통해서 결과!!
System.out.println(sb.toString().trim());
}
}
후기
오랜만에 집중해서 문제를 푼 것 같은데, 오롯이 나만의 힘으로 풀지는 못했지만 머리를 쓰는 시간은 꽤 상쾌하고 뿌듯했던 것 같습니다!
'Coding Test > Baekjoon' 카테고리의 다른 글
[백준] 11559 Puyo Puyo (java) (0) | 2023.09.04 |
---|---|
[백준] 1806 부분합, 자바 (0) | 2023.05.09 |
[백준] 2251 물통, 자바 (0) | 2023.04.18 |
[백준] 15684 사다리 조작, 자바 (0) | 2023.04.15 |
[백준] 15683 감시, 자바 (0) | 2023.04.11 |