문제는 다음과 같다.
https://www.acmicpc.net/problem/2021
풀이는 다음과 같다. (맞은 풀이)
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer> [] A, B;
//A는 어떤 역이 속한 호선 (A[1] = {2, 3, 4} == 1번역은 2, 3, 4 호선 지남)
//B는 호선에 속한 역 (B[2] = {5, 6} == 2호선의 역이 5번, 6번역)
static int N,L;
static boolean[] visited;
static int end;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//최소 환승 경로를 구하는 프로그램을 작성하시오. 실제 경로를 구할 필요는 없고, 환승 회수만을 구하면 된다.
//첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다.
StringTokenizer st1 = new StringTokenizer(br.readLine());
N = Integer.parseInt(st1.nextToken());
L = Integer.parseInt(st1.nextToken());
A = new ArrayList[N+1];
B = new ArrayList[L+1];
visited = new boolean[N+ L + 1]; //1~N 까지는 역, N+1 ~ N+L 까지는 호선
for(int i = 1 ; i <= N ; i++) {
A[i] = new ArrayList<>();
}
for(int i = 1 ; i <= L ; i++) {
B[i] = new ArrayList<>();
}
//다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다.
for(int i = 1 ; i <= L ; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
while(true) {
int num = Integer.parseInt(st2.nextToken());
if(num == -1) break;
B[i].add(num); //호선에 속한 역
A[num].add(i); //역이 지나는 호선
}
}
//마지막 줄에는 출발지 역의 번호와 목적지 역의 번호가 주어진다.
StringTokenizer st3 = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st3.nextToken());
end = Integer.parseInt(st3.nextToken());
int answer = BFS(start);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
//역 번호는 1부터 N까지의 정수로 표현된다. 각 노선의 길이의 합은 1,000,000을 넘지 않는다.
}
static int BFS(int start) {
PriorityQueue<Station> q = new PriorityQueue<>();
visited[start] = true; //출발역
for(int line : A[start]) {
q.add(new Station(start, line, 0));
visited[N+line] = true; //출발역의 호선들
}
while(!q.isEmpty()) {
Station curStation = q.poll();
int curNum = curStation.num;
int curLine = curStation.line;
int curCnt = curStation.cnt;
if(curNum == end) return curCnt;
//뽑은 역의 호선들
for(int nextLine : A[curNum]) {
if(!visited[N+nextLine]) {
visited[N+nextLine] = true;
q.add(new Station(curNum, nextLine, curCnt+1));
}
}
//현재 호선의 다른역들
for(int nextNum : B[curLine]) {
if(!visited[nextNum]) {
visited[nextNum] = true;
q.add(new Station(nextNum, curLine, curCnt));
}
}
}
//큐 빌때까지 못찾으면 아예 환승 불가.
return -1;
}
//환승기준 우선순위 큐 만들 station 클래스
static class Station implements Comparable<Station>{
int num, line, cnt;
public Station (int num, int line, int cnt) {
this.num = num;
this.line = line;
this.cnt = cnt;
}
public int compareTo(Station s) {
if(this.cnt > s.cnt) return 1;
return -1;
}
}
}처음 풀이는 아래와 같이 풀었고,
해당 코드가 틀린 부분은 없지만, 메모리 이슈로 인해
메모리 초과가 되었다.
그럼 메모리를 줄일 수 있는 부분이 어디있을까..
싶다가 visited 방문배열을 2차원에서 1차원으로,
즉 visited[호선][역번호] 에서
visited[1~N까지는 역번호, N+1~N+L+1까지는 호선]으로 바꿔주었다.
그렇게 바뀌면 호선과 역번호가 최댓값이라는 가정 하에
메모리 공간이
2차원 배열 공간 10만 * 10만 = 100억 에서
1차원 배열 공간 10만 + 10만 = 20만 까지 줄일 수 있게 된다.
해당 내용만 바뀐게
2차원 아래 풀이 -> 1차원 위 풀이 의 순서이다
그 부분만 바꾸어 주니까 맞았습니다가 나왔다.
(메모리 이슈로 틀린 풀이)
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer> [] A, B;
//A는 어떤 역이 속한 호선 (A[1] = {2, 3, 4} == 1번역은 2, 3, 4 호선 지남)
//B는 호선에 속한 역 (B[2] = {5, 6} == 2호선의 역이 5번, 6번역)
static boolean[][] visited;
static int end;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//최소 환승 경로를 구하는 프로그램을 작성하시오. 실제 경로를 구할 필요는 없고, 환승 회수만을 구하면 된다.
//첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다.
StringTokenizer st1 = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st1.nextToken());
int L = Integer.parseInt(st1.nextToken());
A = new ArrayList[N+1];
B = new ArrayList[L+1];
visited = new boolean[L+1][N+1];
for(int i = 1 ; i <= N ; i++) {
A[i] = new ArrayList<>();
}
for(int i = 1 ; i <= L ; i++) {
B[i] = new ArrayList<>();
}
//다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다.
for(int i = 1 ; i <= L ; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
while(true) {
int num = Integer.parseInt(st2.nextToken());
if(num == -1) break;
B[i].add(num); //호선에 속한 역
A[num].add(i); //역이 지나는 호선
}
}
//마지막 줄에는 출발지 역의 번호와 목적지 역의 번호가 주어진다.
StringTokenizer st3 = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st3.nextToken());
end = Integer.parseInt(st3.nextToken());
int answer = BFS(start);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
//역 번호는 1부터 N까지의 정수로 표현된다. 각 노선의 길이의 합은 1,000,000을 넘지 않는다.
}
static int BFS(int start) {
PriorityQueue<Station> q = new PriorityQueue<>();
for(int line : A[start]) {
q.add(new Station(start, line, 0));
}
while(!q.isEmpty()) {
Station curStation = q.poll();
int curNum = curStation.num;
int curLine = curStation.line;
int curCnt = curStation.cnt;
if(visited[curLine][curNum]) continue;
visited[curLine][curNum] = true;
if(curNum == end) return curCnt;
//뽑은 역의 호선들
for(int nextLine : A[curNum]) {
if(!visited[nextLine][curNum]) {
q.add(new Station(curNum, nextLine, curCnt+1));
}
}
//현재 호선의 다른역들
for(int nextNum : B[curLine]) {
if(!visited[curLine][nextNum]) {
q.add(new Station(nextNum, curLine, curCnt));
}
}
}
//큐 빌때까지 못찾으면 아예 환승 불가.
return -1;
}
//환승기준 우선순위 큐 만들 station 클래스
static class Station implements Comparable<Station>{
int num, line, cnt;
public Station (int num, int line, int cnt) {
this.num = num;
this.line = line;
this.cnt = cnt;
}
public int compareTo(Station s) {
if(this.cnt > s.cnt) return 1;
return -1;
}
}
}문제 자체는 아래 문제와 굉장히 비슷하다.
다익스트라 알고리즘을 알고 있다면,
(https://www.youtube.com/watch?v=XIwiZZr2l5I)
주석을 읽으며 어렵지 않게 이해할 수 있을 내용이다.
https://velog.io/@dlsrjsdl6505/%EB%B0%B1%EC%A4%80-16166-%EC%84%9C%EC%9A%B8%EC%9D%98-%EC%A7%80%ED%95%98%EC%B2%A0-%EC%9E%90%EB%B0%94
풀이도 마찬가지로 비슷하게 풀었다.
요새 부쩍 알고리즘 문제를 풀며 메모리 이슈가 많이 나온다.
메모리를 줄일 수 있는법을 항상 숙지하고 있자.
반갑습니다~! 좋은하루 보내세요 :)