programmers/DFS-BFS
백준 2593번 : 엘리베이터 [자바]
Meluu_
2025. 7. 11. 10:01
🧫 문제 분석
✔️ 출처
📖 문제
최단경로 + BFS + 역추적 문제
이문제를 풀면서 메모리초과가 진짜 자꾸 나서
정말 힘들었다.
여러번의 테스트 끝에 알아낸 것은
컬렉션에서
for (int i : list)향상된 for문(for-each)는 내부적으로 Iterator 객체를 생성해서 순회한다.
때문에 수많은 엘리베이터를 갖는 리스트를 foreach로 접근했으니
메모리초과될 수밖에 없었다.
많은 양의 요소를 담는 컬렉션 객체는 되도록이면 for-each문을 사용하지 말아야겠다.
그리고 거리는 dist배열로 따로 빼자.
괜히 큐에 같이넣어서 메모리초과뜬다.
🔅 문제 풀이 [다익스트라]
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] dist, parent;
static List<Integer>[] elevators; // idx = 엘레베이터, element = 각 층
static List<Integer>[] floors; // idx = 층 , element = 가능한 엘레베이터
static final int MAX = Integer.MAX_VALUE;
static class Node implements Comparable<Node> {
int elevator, dist;
public Node(int elevator, int dist) {
this.elevator = elevator;
this.dist = dist;
}
@Override
public int compareTo(Node o) {
return dist - o.dist;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
elevators = new List[M + 1];
floors = new List[N + 1];
dist = new int[M + 1];
parent = new int[M + 1];
Arrays.fill(dist, MAX);
for (int i = 0; i < M + 1; i++) {
elevators[i] = new ArrayList<>();
}
for (int i = 0; i < N + 1; i++) {
floors[i] = new ArrayList<>();
}
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// 각 층 및 엘레베이터 추가
for (int j = x; j <= N; j+= y) {
elevators[i].add(j);
floors[j].add(i);
}
}
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
dijkstra(A, B);
}
private static void dijkstra(int start, int end) {
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작 위치가 있는 엘레베이터는 바로 현재 층이므로 거리가 1
for (int elevator : floors[start]) {
pq.offer(new Node(elevator, 1));
parent[elevator] = -1; // -1로 시작지점을 표시
dist[elevator] = 1;
}
while (!pq.isEmpty()) {
Node current = pq.poll();
if (dist[current.elevator] < current.dist) continue;
// 현재 엘레베티어에 있는 모든 층을 꺼낸다.
for (int floor : elevators[current.elevator]) {
// 꺼낸 각각의 층이 탈 수 있는 모든 엘레베이터를 꺼낸다.
for (int i = 0; i < floors[floor].size(); i++) {
int elevator = floors[floor].get(i);
// 해당 엘레베이터로 가는 비용이 현재 엘베를 갈아타고 가는게 비용이 더 적다면 갱신
if (dist[elevator] > current.dist + 1) {
dist[elevator] = current.dist + 1;
parent[elevator] = current.elevator;
pq.offer(new Node(elevator, dist[elevator]));
}
}
}
}
int min = MAX;
int minElevator = 0;
for (int elevator : floors[end]) {
if (dist[elevator] < min) {
min = dist[elevator];
minElevator = elevator;
}
}
if (min == MAX) {
System.out.println(-1);
}else {
System.out.println(min);
Stack<Integer> stack = new Stack<>();
int cur = minElevator;
while (cur != -1) {
stack.push(cur);
cur = parent[cur];
}
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
}🔅 문제 풀이 [BFS]
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static List<Integer>[] floors;
static List<Integer>[] elevators;
static boolean[] visited;
static int[] parent;
static int[] dist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
elevators = new List[m + 1];
floors = new List[n + 1];
visited = new boolean[m + 1];
parent = new int[m + 1];
for (int i = 0; i <= m; i++) {
elevators[i] = new ArrayList<>();
}
for (int i = 0; i <= n; i++) {
floors[i] = new ArrayList<>();
}
for (int i = 1; i <= m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int plus = Integer.parseInt(st.nextToken());
for (int j = start; j <= n; j += plus) {
elevators[i].add(j);
floors[j].add(i);
}
}
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
dist = new int[m + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
int answer = bfs(A, B);
if (answer == -1) {
System.out.println(answer);
} else {
StringBuilder sb = new StringBuilder();
sb.append(answer).append("\n");
int min = Integer.MAX_VALUE;
int minElevator = 0;
for (Integer i : floors[B]) {
if (min > dist[i]) {
min = dist[i];
minElevator = i;
}
}
int cur = minElevator;
Stack<Integer> stack = new Stack<>();
while (cur != -1) {
stack.push(cur);
cur = parent[cur];
}
while (!stack.isEmpty()) {
sb.append(stack.pop()).append("\n");
}
System.out.print(sb.toString());
}
}
// floors : 각 층에 있는 엘레베이터 리스트
// elevaotrs : 각 엘레베이터에 있는 층들
private static int bfs(int start, int end) {
Queue<Integer> q = new LinkedList<>();
for (int elevator : floors[start]) {
q.add(elevator);
dist[elevator] = 1;
parent[elevator] = -1;
visited[elevator] = true;
}
while (!q.isEmpty()) {
int cur = q.poll();
for (int floor : elevators[cur]) {
if (floor == end) {
return dist[cur];
}
for (int i = 0; i < floors[floor].size(); i++) {
int nextElevator = floors[floor].get(i);
if (!visited[nextElevator]) {
visited[nextElevator] = true;
dist[nextElevator] = dist[cur] + 1;
parent[nextElevator] = cur;
q.add(nextElevator);
}
}
}
}
return -1;
}
}❗ 오답노트 / 필요한 지식
- 컬렉션객체는 for-each사용시 iterator를 사용한다는것을 다시한번 리마인드하게되었다.