[ 백준 ]
- 18352번 특정 거리의 도시 찾기
: 맨 처음에 첫 번째 코드로 풀고 예시 케이스 모두 통과하길래 혼자서 기뻐했으나, 제출하니까 시간초과 뜸 ㅠ
그래도 이제 BFS는 혼자서 어느정도 풀 수 있는 것 같다. 굿굿,,
해설보니까 나와 다르게 푼 점은 visited[]에 boolean 대신 int 타입을 써서 거리를 직접 입력했다는 것인데... (나는 depth 사용)
내가 만든 코드는 거리가 K를 넘어가는 시점에서 break하여 loop를 탈출하므로 더 효율적일 것 같은데 왜 시간 초과 뜨는지 모르겠음.. 조건문이 많아서 그런가..
답지 참고해서 두 번째 코드로 다시 제출해서 통과했다.
import java.io.*;
import java.util.*;
public class Main {
public static ArrayList<Integer>[] map;
public static boolean[] visited;
public static int depth;
public static PriorityQueue<Integer> answer;
public static int N, M, K, X;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //선언
//입력값 받기
StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
N = Integer.parseInt(stringTokenizer.nextToken());
M = Integer.parseInt(stringTokenizer.nextToken());
K = Integer.parseInt(stringTokenizer.nextToken());
X = Integer.parseInt(stringTokenizer.nextToken());
//초기화
map = new ArrayList[N + 1];
for (int i = 1; i < N + 1; i++) {
map[i] = new ArrayList<>();
}
visited = new boolean[N + 1];
depth = 0;
//엣지 연결
for (int i = 0; i < M; i++) {
stringTokenizer = new StringTokenizer(br.readLine());
int S = Integer.parseInt(stringTokenizer.nextToken());
int E = Integer.parseInt(stringTokenizer.nextToken());
map[S].add(E);
}
//X에서 출발하여 BFS 최단거리가 K인 도시를 오름차순으로 출력. 없으면 -1 출력.
PriorityQueue bfs = BFS(X);
if (bfs.isEmpty()) System.out.println("-1");
for (int i = 0; i < bfs.size(); i++) {
System.out.println(bfs.poll());
}
}
private static PriorityQueue BFS(int X) {
answer = new PriorityQueue();
Queue<Integer> queue = new LinkedList<>();
queue.add(X);
visited[X] = true;
while (!queue.isEmpty()) {
int now = queue.poll();
if (queue.isEmpty()) depth++;
if (depth > K) break;
for (int i = 1; i < map.length; i++) {
if (!visited[i] && map[now].contains(i)) {
queue.add(i);
visited[i] = true;
if (depth == K) answer.add(i);
}
}
}
return answer;
}
}import java.io.*;
import java.util.*;
public class Main {
public static ArrayList<Integer>[] map;
public static int[] visited;
public static PriorityQueue<Integer> answer;
public static int N, M, K, X;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //선언
//입력값 받기
StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
N = Integer.parseInt(stringTokenizer.nextToken());
M = Integer.parseInt(stringTokenizer.nextToken());
K = Integer.parseInt(stringTokenizer.nextToken());
X = Integer.parseInt(stringTokenizer.nextToken());
//초기화
map = new ArrayList[N + 1];
for (int i = 1; i < N + 1; i++) {
map[i] = new ArrayList<>();
}
visited = new int[N + 1];
for (int i = 1; i < N + 1; i++) {
visited[i] = -1;
}
//엣지 연결
for (int i = 0; i < M; i++) {
stringTokenizer = new StringTokenizer(br.readLine());
int S = Integer.parseInt(stringTokenizer.nextToken());
int E = Integer.parseInt(stringTokenizer.nextToken());
map[S].add(E);
}
//X에서 출발하여 BFS 최단거리가 K인 도시를 오름차순으로 출력. 없으면 -1 출력.
BFS(X);
answer = new PriorityQueue();
for(int i=0; i<=N; i++){
if(visited[i]==K) answer.add(i);
}
if(answer.isEmpty()) System.out.println("-1");
for(int a : answer){
System.out.println(a);
}
}
private static void BFS(int X) {
Queue<Integer> queue = new LinkedList<>();
queue.add(X);
visited[X]++;
while (!queue.isEmpty()) {
int now = queue.poll();
for (int i : map[now]) {
if (visited[i] == -1) {
queue.add(i);
visited[i] = visited[now] + 1;
}
}
}
}
}[ 자료구조 & 알고리즘 ]
- 그래프 표현
- 에지리스트
- 가중치 없을 때 A[2][]
- 가중치 있을 때 A[3][]
- 벨만포드, 크루스칼 알고리즘에 이용
- 인접 행렬
- A[N][N]
- 노드 중심
- 노드 3만 개 넘으면 자바 힙 스페이스 에러 발생
- 인접 리스트
- 가중치 없을 때 ArrayList< Integer>[N]
- 가중치 있을 때 ArrayList< Node>[N]
- 에지리스트
[ 유어클래스 다시 읽기 ]
- section3. API 문서화
- 자동화 필요
- Spring Rest Docs(테스트 필수), Swagger, Postman
- open api 3.0 글로벌 표준 양식
- @AutoConfigureRestDocs
- @EnableJpaAuditing, @MockBean(JpaMetamodelMappingContext.class)
- section3. 애플리케이션 빌드 / 실행 / 배포
- 프로파일(Profile) : 여러 개의 환경 설정 이용하기
--spring.profiles.active=local
--spring.profiles.active=server
https://zzang9ha.tistory.com/415
- 프로파일(Profile) : 여러 개의 환경 설정 이용하기
$ java -jar SNAPSHOT.jar --spring.profiles.active=local[ 느낀 점 ]
오전에 SQL 노랭이 공부 완료.
부트캠프 수료 후 약간의 휴식 기간을 가진 뒤, 다시 공부 및 취준을 병행한 지 약 한 달이 좀 넘었다.
이전에 배웠던 내용들을 다시 읽어보고 있는데, 오늘로 section3까지 다시 보기 성공.
이제 section4 하나 남았다.
section4까지 다 읽은 후에는 집에 있는 책 <자바 코딩 인터뷰 완벽 가이드> by 안겔 레오나르드 를 읽을 생각이다.
오늘 본 API 문서화는 RestDocs 관련해서 jmt practice 라든지, pre-project에서 많은 추억이 있어서, 읽으면서 그때 생각이 났다. 나도 팀원들도 같이 고생했던 기억.
내 벨로그와 깃헙 레포지토리에 들어가서 그 당시의 기록 및 코드를 다시 보기도 했다.
코딩테스트 준비는 너무 스트레스 받지 않고, 매일 하나씩만 푼다는 마음으로 해야겠다.
