Skip to content

Latest commit

 

History

History
307 lines (249 loc) · 12.3 KB

bj_2021.md

File metadata and controls

307 lines (249 loc) · 12.3 KB

2021. 최소 환승 경로

Summary

🙇‍♂️ URL : https://www.acmicpc.net/problem/2021
🤷‍♂️ Difficulty: ?
💆‍♂️ Submissions : Success

Source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class App {

    static int N, L;
    static boolean[] visitedLine;
    static boolean[] visitedStation;

    static HashMap<Integer, ArrayList<Integer>> lineInfo = new HashMap<>();      // 노선 별 정차하는 역의 수 -> 노선 만큼의 갯수 할당
    static HashMap<Integer, ArrayList<Integer>> stationInfo = new HashMap<>();   // 역 별 정차하는 노선의 수 -> 역 만큼의 갯수 할당
    
    public static void main(String[] args) throws Exception {
        
        // 어떤 도시의 지하철 노선에 대한 정보가 주어졌을 때, 출발지에서 목적지까지의 최소 환승 경로를 구하는 프로그램을 작성하시오. 실제 경로를 구할 필요는 없고, 환승 회수만을 구하면 된다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 첫째 줄에 역(Station)의 개수 N(1≤N≤100,000), 노선(Line)의 개수 L(1≤L≤100,000)이 주어진다. 
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        visitedStation = new boolean[N+1];
        visitedLine = new boolean[L+1];

        for(int i=1; i<=L; i++) {
            // 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며,
            String[] l = br.readLine().split(" ");
            for (String station : l) {
                int s = Integer.parseInt(station);
                if (s == -1) {
                    // 각 줄의 마지막에는 -1이 주어진다.
                    break;
                }
                // 역 마다 정차하는 노선 해시맵 생성 (lineInfo)
                if (lineInfo.get(i) == null) {
                    ArrayList<Integer> stationsWhereLineStop = new ArrayList<>();
                    stationsWhereLineStop.add(s);
                    lineInfo.put(i, stationsWhereLineStop);
                } else {
                    lineInfo.get(i).add(s);
                }

                // 노선마다 정차하는 역 해시맵 생성 (stationInfo)
                if (stationInfo.get(s) == null) {
                    ArrayList<Integer> lineInStation = new ArrayList<>();
                    lineInStation.add(i);
                    stationInfo.put(s, lineInStation);
                } else {
                    stationInfo.get(s).add(i);
                }
            }
        }

        // 마지막 줄에는 출발지 역의 번호(startStation)와 목적지 역(endStation)의 번호가 주어진다
        st = new StringTokenizer(br.readLine());
        int startStation = Integer.parseInt(st.nextToken());    
        int endStation = Integer.parseInt(st.nextToken());

        System.out.println(solution(startStation, endStation));
    }

    public static int solution(int start, int end) {

        // 현재 역의 정보를 저장할 자료구조
        class Ticket {
            int station;
            int line;
            int transferCount;
            public Ticket(int station, int line, int transferCount) {
                this.station = station;
                this.line = line;
                this.transferCount = transferCount;
            }
        }


        // 환승 횟수를 우선순위로 하는 큐 생성
        PriorityQueue<Ticket> queue = new PriorityQueue<>(
            Comparator.comparingInt(t -> t.transferCount)
        );

        // 시작 역에서 탈 수 있는 모든 노선 정보를 먼저 우선순위 큐에 저장
        ArrayList<Integer> linesInStartStation = stationInfo.get(start);
        for(int line : linesInStartStation) {
            // {현재 역, 역에서 탈 수 있는 노선, 환승 횟수} 객체 생성 및 저장 
            queue.add(new Ticket(start, line, 0));
            // 역에 있는 모든 노선은 방문 처리
            visitedLine[line] = true;
        }

        while(!queue.isEmpty()) {
            
            Ticket current = queue.poll();
            
            // (종료) 도착 역과 동일하면 지금까지 환승한 횟수 반환 
            if(current.station == end) {
                return current.transferCount;
            }

            // 특정 노선으로 갈 수 있는 모든 역 목록 
            ArrayList<Integer> stations = lineInfo.get(current.line);

            for(int nextStation : stations) {
                // 다음 역이 아직 방문하지 않은 역인 경우,
                if(visitedStation[nextStation] == false) {
                    visitedStation[nextStation] = true;
                    // 환승 없이 해당 노선을 타고 그대로 다음 역으로 갈 수 있으므로 => transferCount 증가 안함
                    queue.add(new Ticket(nextStation, current.line, current.transferCount));
                }

                // 다음에 이동할 역에서 환승할 수 있는 노선 목록
                ArrayList<Integer> lines = stationInfo.get(nextStation);
                for(int nextLine : lines) {
                    // 아직 다음 노선을 이용해본적이 없는 경우,
                    if(visitedLine[nextLine] == false) {
                        visitedLine[nextLine] = true;
                        // 해당 역에서 다른 노선으로 환승해서 가는 경우
                        queue.add(new Ticket(nextStation, nextLine, current.transferCount+1));
                    }
                }
            }
        }
        return -1;
    }
}

How to Approach

1. 문제 핵심, 목표

본 문제의 핵심은 '한 지하철 역에서 다른 지하철 역으로 이동할 때, 가장 적은 횟수의 노선을 사용하는 것'이다.

2. 노선 별 정차역 리스트, 역 별 지나가는 노선 리스트 생성

먼저 문제를 통해 노선 별로 정차하는 역의 리스트와 역 별로 정차하는 노선의 리스트 각각을 만들었다. 다른 분들의 문제 해설을 보면 중첩된 구조의 ArrayList 또는 배열 형태의 ArrayList를 사용하는데, 나는 해시맵 구조로 하면 더 빠르게 접근할 수 있을 것이라 판단하여 이를 이용하였다.

static HashMap<Integer, ArrayList<Integer>> lineInfo = new HashMap<>();      // 노선 별 정차하는 역의 수 -> 노선 만큼의 갯수 할당
static HashMap<Integer, ArrayList<Integer>> stationInfo = new HashMap<>();   // 역 별 정차하는 노선의 수 -> 역 만큼의 갯수 할당

각 해시맵에 문제에서 주어지는 값을 알맞게 삽입하였다.

...
for(int i=1; i<=L; i++) {
    // 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며,
    String[] l = br.readLine().split(" ");
    for (String station : l) {
        ...
        // 역 마다 정차하는 노선 해시맵 생성 (lineInfo)
        if (lineInfo.get(i) == null) {
            ArrayList<Integer> stationsWhereLineStop = new ArrayList<>();
            stationsWhereLineStop.add(s);
            lineInfo.put(i, stationsWhereLineStop);
        } else {
            lineInfo.get(i).add(s);
        }

        // 노선마다 정차하는 역 해시맵 생성 (stationInfo)
        if (stationInfo.get(s) == null) {
            ArrayList<Integer> lineInStation = new ArrayList<>();
            lineInStation.add(i);
            stationInfo.put(s, lineInStation);
        } else {
            stationInfo.get(s).add(i);
        }
    }
}
...

문제 샘플에 해당하는 정보를 토대로 만들어진 값을 출력하면 아래와 같을 것이다.

# lineInfo
- [1] : 1 2 3 4 5 
- [2] : 9 7 10 
- [3] : 7 6 3 8 

# stationInfo
- [1] : 1 
- [2] : 1 
- [3] : 1 3 
- [4] : 1 
- [5] : 1 
- [6] : 3 
- [7] : 2 3 
- [8] : 3 
- [9] : 2 
- [10] : 2

3. 역 재방문 또는 노선 재탑승을 막기 위한 배열 선언

추가로 한번이라도 방문한 역 또는 사용한 노선을 체크할 수 있는 배열을 선언한다. 이전에 방문했던 역에 다시 방문하거나 이전에 사용했던 노선을 다시 사용하는 것은, 동일한 동작을 계속 반복하는 loop 형태를 만들기 때문에 visited 여부를 확인한다. 각 배열의 크기는 문제로부터 전달받은 값을 이용한다.

static boolean[] visitedLine;
static boolean[] visitedStation;
...
visitedStation = new boolean[N+1];
visitedLine = new boolean[L+1];

4. BFS

본 문제가 '출발지부터 목적지까지 갈 수 있는 모든 경우의 수'를 확인하는 것이 목표였다면 DFS를 사용했지만, 최단 환승경로를 확인하면 되는 문제이기 때문에 BFS를 사용한다.

4.1. 현 시점에서의 이동정보를 담는 클래스 생성

현 시점에서 역의 위치와 현재 해당 역으로 이동할 때 사용중인 노선, 그리고 여기까지 올 동안 환승한 총 횟수를 하나의 클래스로 만들어서 관리한다.

class Ticket {
    int station;
    int line;
    int transferCount;
    public Ticket(int station, int line, int transferCount) {
        this.station = station;
        this.line = line;
        this.transferCount = transferCount;
    }
}

4.2. 우선순위 큐 생성

BFS는 기본적으로 큐(Queue)를 사용한다. 본 문제에서는 동일한 역이라 하더라도 올 때 까지 사용한 노선의 수는 제각각이기 때문에, 큐의 순서를 항상 관리하여 가장 적은 환승 횟수를 먼저 확인하도록 하는 것이 중요하다. 그리하여 우선순위 큐를 사용하였고, 해당 큐는 환승 횟수를 기준으로 오름차순하도록 구성하였다.

PriorityQueue<Ticket> queue = new PriorityQueue<>(
    Comparator.comparingInt(t -> t.transferCount)
);

4.3. 데이터 확인

먼저 시작역에서 탑승 가능한 노선 목록을 모두 큐에 삽입한다.

// 시작 역에서 탈 수 있는 모든 노선 정보를 먼저 우선순위 큐에 저장
ArrayList<Integer> linesInStartStation = stationInfo.get(start);
for(int line : linesInStartStation) {
    // {현재 역, 역에서 탈 수 있는 노선, 환승 횟수} 객체 생성 및 저장 
    queue.add(new Ticket(start, line, 0));
    // 역에 있는 모든 노선은 방문 처리
    visitedLine[line] = true;
}

그리고 큐를 모두 확인할 때 까지 아래의 순서를 반복한다.

  1. 큐에 있는 이동정보 클래스를 하나 빼낸다.
  • 해당 이동정보에 적혀있는 역의 이름이 목적지와 동일하면 바로 종료
  1. 아직 방문해보지 않은 역인지 확인
  • 해당 역에서부터 동일한 노선으로 이동할 수 있는(환승 No) 역을 찾아서 큐에 삽입
  • 해당 역에서 환승할 수 있는 노선의 목록을 보고, 아직 한번도 이용하지 않은 노선을 확인
  • 갈아탄 노선으로부터 갈 수 있는 다른 역을 찾아 큐에 삽입

이를 코드로 표현하면 아래와 같다.

while(!queue.isEmpty()) {
    Ticket current = queue.poll();
    
    // (종료) 도착 역과 동일하면 지금까지 환승한 횟수 반환 
    if(current.station == end) {
        return current.transferCount;
    }

    // 특정 노선으로 갈 수 있는 모든 역 목록 
    ArrayList<Integer> stations = lineInfo.get(current.line);

    for(int nextStation : stations) {
        // 다음 역이 아직 방문하지 않은 역인 경우,
        if(visitedStation[nextStation] == false) {
            visitedStation[nextStation] = true;
            // 환승 없이 해당 노선을 타고 그대로 다음 역으로 갈 수 있으므로 => transferCount 증가 안함
            queue.add(new Ticket(nextStation, current.line, current.transferCount));
        }

        // 다음에 이동할 역에서 환승할 수 있는 노선 목록
        ArrayList<Integer> lines = stationInfo.get(nextStation);
        for(int nextLine : lines) {
            // 아직 다음 노선을 이용해본적이 없는 경우,
            if(visitedLine[nextLine] == false) {
                visitedLine[nextLine] = true;
                // 해당 역에서 다른 노선으로 환승해서 가는 경우
                queue.add(new Ticket(nextStation, nextLine, current.transferCount+1));
            }
        }
    }
}