백준 환승(5214)
1. 힌트
1) 하이퍼튜브를 타고 이동하는 경우 간선의 가중치는 이고 하이퍼튜브에서 내려서 다른 하이퍼튜브를 이용할 때의 가중치를 로 정의할 수 있습니다.
2) 그래프를 구성하는 것이 핵심입니다. 하이퍼 튜브로 연결된 정점끼리 개의 간선을 모두 연결하면 간선의 개수가 너무 많아집니다. 하이퍼튜브로 직접적으로 이어진 정점을 가중치가 인 간선으로 이어줍니다.
3) 입력으로 주어지는 배열을 곧이 곧대로 그래프라고 생각하고 번째 하이퍼루프, 번째 역으로 정점을 정의하고, 좌우로 인접한 역끼리는 가중치가 인 간선으로 정의하고, 다른 하이퍼루프를 이동하는 경우는 가중치가 이 되도록 구현할 수 있습니다.
2. 접근
1) 그래프
그래프를 구성하고 BFS를 이용하면 최단 거리를 구할 수 있습니다. 이 문제에서 거리는 중간 과정에서 방문한 역의 개수입니다. 그런데 하이퍼루프를 이용하면 역을 방문하지 않고도 이동할 수 있기 때문에 그래프의 구성을 조금 달리 할 필요가 있습니다.
그래프의 정점의 정의를 번째 역으로 정의해봅시다. 만약 어떤 정점이 이라면 현재 몇 번째 하이퍼루프에 타고있는 걸까요?
알 수가 없습니다. 따라서 정점의 정의에 하이퍼루프 번호를 추가해서 번째 하이퍼 루프, 번째 역으로 정의해봅시다. 이러면 그래프의 상태 공간의 크기가 으로 너무 커집니다.
따라서 그래프를 입력으로 주어지는 배열처럼 정의합시다. 번째 하이퍼 루프, 번째 하이퍼루프의 번째 역
이번엔 그래프의 간선을 정의해야합니다. 간선의 가중치는 하이퍼루프에서 내리는 경우 이고 하이퍼루프를 타고 이동하는 경우는 입니다. 하이퍼루프 내의 모든 정점 간에 가중치 짜리 간선을 이어줄 필요 없이 바로 왼쪽과 바로 오른쪽 정점간에 간선을 이어주기만 해도 됩니다.
하이퍼루프에서 내리는 경우는 모든 하이퍼루프간에 가중치 짜리 간선을 이어줄 수 있습니다.
3. 구현
1) 0-1 BFS
간선에 가중치가 있는 그래프에서 최단 거리는 Dijkstra로 구하는 것이 일반적이지만, 우리가 구성한 그래프에서는 가중치가 혹은 이기때문에 Deque를 사용하여 0-1 BFS를 해줄 수 있습니다.
2) 하이퍼루프간 간선
는 번째 하이퍼루프와 연결된 다른 하이퍼루프를 저장합니다. 중복될 필요가 없으므로 Set으로 저장합니다. 가장 처음 번 역에서는 어떤 하이퍼루프든지 탈 수 있으므로 모두 Deque에 넣어줍니다.
3) 다른 하이퍼루프로 환승하는 경우
인지 확인합니다. 하필이면 번째 역을 확인하는 이유는 하이퍼루프끼리의 간선의 가중치는 이기 때문에 번째 하이퍼루프를 한번이라도 방문했다면 는 모두 이 아니기 때문입니다.
public class Main {
static final int[] dx = { -1, 1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder bw = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
ArrayList<Set<Integer>> adj = new ArrayList<>(N);
for (int i = 0; i <= N; i++) adj.add(new HashSet<>());
int[][] S = new int[M][K];
Deque<int[]> q = new LinkedList<>();
int[][] dist = new int[M][K];
for (int i = 0; i < M; i++) Arrays.fill(dist[i], -1);
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < K; j++) {
S[i][j] = Integer.parseInt(st.nextToken());
adj.get(S[i][j]).add(i);
if (S[i][j] == 1) {
q.offer(new int[] { i, j });
dist[i][j] = 0;
}
}
}
while (!q.isEmpty()) {
int[] p = q.poll();
int y = p[0]; int x = p[1];
// 하이퍼루프를 따라 양 옆으로 이동하는 경우
for (int d = 0; d < 2; d++) {
int nx = x + dx[d];
if (0 <= nx && nx < K && dist[y][nx] == -1) {
q.offerFirst(new int[] { y, nx });
dist[y][nx] = dist[y][x];
}
}
// 다른 하이퍼루프로 환승하는 경우
for (int there : adj.get(S[y][x])) if (dist[there][0] == -1) {
q.offerLast(new int[] { there, 0 });
dist[there][0] = dist[y][x] + 1;
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < M; i++) {
for (int j = 0; j < K; j++) {
if (S[i][j] == N) {
if (dist[i][j] != -1) {
min = Math.min(min, dist[i][j]);
}
}
}
}
if (min == Integer.MAX_VALUE) min = -1;
else if (N != 1) min += 2;
else min = 1;
bw.append(min).append("\n");
System.out.print(bw);
}
}
Author And Source
이 문제에 관하여(백준 환승(5214)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@axiom0510/b5214저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)