스터디 문제인데 괜찮은 문제인 것 같아 리뷰를 씁니다.
스터디원 모두 다양한 방법으로 풀었기도 하고, 질문 게시판에 글이 몇 개 없기도 해서 작성합니다.
🔗 문제
https://www.acmicpc.net/problem/16166
✏️ 풀이
이 문제의 핵심은 큰 수의 역 번호를 가지고 어떻게 최소 환승 횟수를 구하는 가이다.
그리고 호선과 역의 연결을 어떻게 자료구조를 저장할지 생각해 보는 것!
1. Mapper 설계
N의 최대 크기는 2^31승인데 입력 타입을 int로 받아도 정답이 잘 나온다. (테스트 케이스가 부실?..)
HashMap<Long, Integer> mapper;
Long -> [hashing] -> idx (고작 0~100임)
문제를 잘 보면 호선은 최대 10개, 각 호선마다 최대의 10개의 역
즉, 호선의 값은 크지만 최대 개수는 100개 밖에 되지 않는다.
2. 호선과 역의 저장 장법
나는 일단 아래처럼 자료구조를 만들어서 풀었다.
교대에서 2호선, 4호선으로 갈 수 있다! + 2호선, 4호선에 에 교대가 있다
이걸 어떻게 저장하면 좋을까를 생각하면 이해가 될 듯!!
이 방법이 가장 효율적인 것 같아 2개의 컨테이너를 만들었다.
static Map<Integer, List<Integer>> station = new HashMap(); // station 번호 넣으면 어떤 라인에 속하는지 알려줌
static List<Integer>[] line = new ArrayList[11]; // line 넣으면 어떤 station있는지 알려줌
생각해 본 풀이 방법들
유니온 파인드 + 다익스트라
먼저 start, end역이 같은 역인지 판별하기 위해서 유니온 파인드를 사용한다.
그 후, 다익스트라를 이용해서 다른 역으로 갈 때마다 환승 횟수 +1을 해주려고 했다.
그러나, 문제가 원하는 것은 최소 환승 횟수이기에 유니온 파인드가 굳이..라는 생각이 들었다.
dfs (156ms)
매개변수로 현재 역과 현재까지의 환승 횟수를 매개변수로 넘긴다.
최소 환승 횟수를 구하는 문제인데 끝까지 가본다?.. 역시나 불필요하지만 이걸로도 풀리긴 한다.
bfs (68ms) Java 3등 .. 💖
start에서 연결된 line에서 아직 방문하지 않은 station들을 훑어본다. 자료구조를 잘 설계해 놓으면 그냥 bfs와 동일하다.
💾 소스
import java.io.*;
import java.util.*;
public class Main {
static int N, start, end;
static Mapper mapper = new Mapper();
static Map<Integer, List<Integer>> station = new HashMap(); // station 번호 넣으면 어떤 라인에 속하는지 알려줌
static List<Integer>[] line = new ArrayList[11]; // line 넣으면 어떤 station있는지 알려줌
static int solve() {
int answer = 0;
if(start == -1 || end == -1) {
return -1;
}
for(final int endLine : station.get(end)) {
for(final int startLine : station.get(start)) {
if(endLine == startLine)
return 0;
}
}
int firstLine = station.get(start).get(0);
Queue<Integer> q = new ArrayDeque<>();
q.add(firstLine);
boolean[] lineVisited = new boolean[11];
lineVisited[firstLine] = true;
while(!q.isEmpty()) {
int qSize = q.size();
while(qSize-- > 0) {
int nowLine = q.poll();
for(int nextStation : line[nowLine]) {
if(nextStation == end) return answer;
for(int nextLine : station.get(nextStation)) {
if(lineVisited[nextLine]) continue;
lineVisited[nextLine] = true;
q.offer(nextLine);
}
}
}
++answer;
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
start = end = -1;
N = Integer.parseInt(st.nextToken());
for(int i=0; i<N; ++i)
line[i] = new ArrayList<>();
for(int _line=0; _line<N; ++_line) {
st = new StringTokenizer(br.readLine());
int K = Integer.parseInt(st.nextToken());
for(int j=0; j<K; ++j) {
Long inp = Long.parseLong(st.nextToken());
int stationIdx = mapper.setMapper(inp);
if(inp == 0L)
start = stationIdx;
line[_line].add(stationIdx); // _line호선에 어떤 역이 있는지 저장
List<Integer> lines = station.get(stationIdx);
if (lines == null) {
lines = new ArrayList<>(); // 새로운 리스트 생성
station.put(stationIdx, lines); // station에 추가
}
lines.add(_line); // _line 추가
}
}
end = mapper.getIdx(Long.parseLong(br.readLine()));
System.out.print(solve());
} // main
static class Mapper {
static int INDEX = 0;
HashMap<Long, Integer> mapper; // 역번호를 인덱스로
Mapper() {
mapper = new HashMap<>();
}
int setMapper(final long num) {
mapper.putIfAbsent(num, ++INDEX);
return getIdx(num);
}
int getIdx(final long num) {
return mapper.getOrDefault(num, -1);
}
}
}