섬 n개가 있고 1번부터 n번까지 번호가 붙어 있다.
섬 사이에는 다리 m개가 있고, 다리 하나 "a b k"는 a번 섬과 b번 섬을 잇는 종류 k의 다리다.
다리는 양쪽으로 건널 수 있고, 건너는 데 정확히 1분이 걸린다.
같은 두 섬을 잇는 다리가 여러 개 있을 수 있다.
여행자는 0분에 1번 섬에 있다.
t분에 다리를 건너기 시작하면 t + 1분에 건너편 섬에 닿는다.
종류 0인 다리는 언제든 건너기 시작할 수 있다.
종류 1인 다리는 t가 홀수일 때만, 종류 2인 다리는 t가 짝수일 때만 건너기 시작할 수 있다(0은 짝수다).
건너기 시작한 다리는 끝까지 건넌다.
섬마다 쉼터가 있는지가 주어진다. sᵢ가 1이면 i번 섬에 쉼터가 있다.
쉼터가 있는 섬에서는 1분씩 몇 번이든 기다릴 수 있다.
쉼터가 없는 섬에서는 기다릴 수 없어서, 닿은 바로 그 분에 다리를 건너기 시작해야 한다. 그 분에 건널 수 있는 다리가 없으면 거기서 더 갈 수 없다.
0분의 1번 섬에서도 마찬가지다. 1번 섬에 쉼터가 없으면 0분에 바로 다리를 건너기 시작해야 한다.
같은 섬과 같은 다리를 몇 번이든 다시 지나도 된다.
섬마다, 여행자가 그 섬에 있을 수 있는 가장 이른 시각(분)을 구하라.
1번 섬의 값은 0이고, 어떻게 해도 닿을 수 없는 섬의 값은 -1이다.
첫 줄에 닿을 수 있는 섬의 수를 출력하라. 1번 섬도 센다.
둘째 줄에 1번부터 n번 섬까지의 값을 차례로 빈칸 하나로 띄워 출력하라.
입력
첫 줄에 n과 m, 둘째 줄에 s₁ … sₙ, 다음 m줄에 줄마다 a, b, k가 주어진다. 한 줄의 수들은 빈칸 하나로 나뉜다. 1 ≤ n ≤ 9,000, 0 ≤ m ≤ 9,000, sᵢ는 0 또는 1, 1 ≤ a, b ≤ n, a ≠ b, k는 0, 1, 2 가운데 하나. 모두 정수다
출력
첫 줄에 닿을 수 있는 섬의 수, 둘째 줄에 섬마다 가장 이른 시각(분) n개. 닿을 수 없으면 -1
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
너비 우선 탐색(BFS)인데, '가 본 섬'이 아니라 '(섬, 분의 홀짝)'을 가 본 것으로 적어야 해요. 예제 1에서 2번 섬에는 1분에 처음 닿지만 홀수 분이라 종류 2인 다리를 못 건너요. 1 → 5 → 6 → 1 → 2로 돌아 4분(짝수)에 다시 2번 섬에 와야 3번 섬으로 가요. 함정 하나: 섬마다 한 번만 들르는 보통 BFS는 2번 섬을 다시 큐에 넣지 않아서 3번, 4번 섬을 -1로 내요. 상태가 2n개이니 답은 두 홀짝 가운데 이른 쪽이에요. 함정 둘: 다리는 닿는 분이 아니라 떠나는 분의 홀짝으로 따져요. 0분에 떠나 1분에 닿는 다리는 '짝수' 쪽이에요. 함정 셋: 기다리기는 쉼터에서만 돼요. 어디서나 기다리게 하면 예제 1의 3번 섬이 3이 되고, 쉼터를 빠뜨리면 예제 2의 3번 섬이 -1이 돼요. 기다리기는 '같은 섬, 반대 홀짝'으로 가는 1분짜리 이동으로 넣으면 돼요. 큐는 Python collections.deque(list.pop(0)은 뒤 칸을 모두 당겨서 느려요), Java ArrayDeque, C# Queue<T>, C++ std::queue를 쓰고, JS·TS·C는 배열과 '머리 번호'로 해요(JS의 shift()도 뒤 칸을 당겨요). 상태는 2 * v + p처럼 수 하나로 묶으면 배열 하나로 돼요. 크레이콘은 목록이 10,000칸까지라 2n칸짜리 새목록(2 * n, -1)은 n이 5,000을 넘으면 멈춰요. 그래서 홀짝마다 목록을 따로 두고(새목록(n, 거짓) 둘), 같은 분에 나온 상태는 홀짝이 모두 같다는 점을 써서 큐 대신 '이번 분의 섬 목록'을 한 층씩 넘겨요.
Pythonmain.py · 44 줄
import sysfrom collections import dequedef main(): data = sys.stdin.buffer.read().split() n, m = int(data[0]), int(data[1]) shelter = [0] + [int(x) for x in data[2:2 + n]] bridges = [[] for _ in range(n + 1)] # bridges[u] = (이웃 섬, 종류)들 pos = 2 + n for _ in range(m): a, b, k = int(data[pos]), int(data[pos + 1]), int(data[pos + 2]) pos += 3 bridges[a].append((b, k)) bridges[b].append((a, k)) # 상태 = (섬, 분의 홀짝). when[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때 when = [-1] * (2 * n + 2) when[2 * 1 + 0] = 0 queue = deque([2]) # list.pop(0)은 뒤 칸을 모두 당겨서 느리다 while queue: state = queue.popleft() u, p = state // 2, state % 2 t = when[state] + 1 q = 1 - p if shelter[u] and when[2 * u + q] == -1: # 쉼터에서 1분 기다린다 when[2 * u + q] = t queue.append(2 * u + q) for v, k in bridges[u]: # 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다 if (k == 0 or (k == 1) == (p == 1)) and when[2 * v + q] == -1: when[2 * v + q] = t queue.append(2 * v + q) # 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽 first = [] for v in range(1, n + 1): times = [x for x in (when[2 * v], when[2 * v + 1]) if x != -1] first.append(min(times) if times else -1) print(sum(1 for x in first if x != -1)) print(" ".join(map(str, first)))main()
JavaScriptmain.js · 51 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const shelter = [0];for (let v = 1; v <= n; v++) shelter.push(data[1 + v]);// bridges[u] = [이웃 섬, 종류]들(다리는 양쪽으로 건넌다)const bridges = Array.from({ length: n + 1 }, () => []);for (let i = 0; i < m; i++) { const a = data[2 + n + 3 * i]; const b = data[3 + n + 3 * i]; const k = data[4 + n + 3 * i]; bridges[a].push([b, k]); bridges[b].push([a, k]);}// 상태 = (섬, 분의 홀짝). time[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때const time = new Array(2 * n + 2).fill(-1);time[2 * 1 + 0] = 0;const queue = [2];// shift()는 뒤의 것을 모두 당겨서 느리다. 머리 번호 head를 옮긴다for (let head = 0; head < queue.length; head++) { const u = queue[head] >> 1; const p = queue[head] & 1; const t = time[queue[head]]; const visit = (v) => { const s = 2 * v + (1 - p); if (time[s] === -1) { time[s] = t + 1; queue.push(s); } }; if (shelter[u] === 1) visit(u); // 쉼터에서 1분 기다린다 for (const [v, k] of bridges[u]) { // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다 if (k === 0 || (k === 1) === (p === 1)) visit(v); }}const first = [];let reached = 0;for (let v = 1; v <= n; v++) { const even = time[2 * v]; const odd = time[2 * v + 1]; // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽 const best = even === -1 ? odd : odd === -1 ? even : Math.min(even, odd); if (best !== -1) reached++; first.push(best);}console.log(reached);console.log(first.join(" "));
TypeScriptmain.ts · 54 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const shelter: number[] = [0];for (let v = 1; v <= n; v++) shelter.push(data[1 + v]);// bridges[u] = [이웃 섬, 종류]들(다리는 양쪽으로 건넌다)type Bridge = [to: number, kind: number];const bridges: Bridge[][] = Array.from({ length: n + 1 }, (): Bridge[] => []);for (let i = 0; i < m; i++) { const a = data[2 + n + 3 * i]; const b = data[3 + n + 3 * i]; const k = data[4 + n + 3 * i]; bridges[a].push([b, k]); bridges[b].push([a, k]);}// 상태 = (섬, 분의 홀짝). time[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때const time: number[] = new Array<number>(2 * n + 2).fill(-1);time[2 * 1 + 0] = 0;const queue: number[] = [2];// shift()는 뒤의 것을 모두 당겨서 느리다. 머리 번호 head를 옮긴다for (let head = 0; head < queue.length; head++) { const u = queue[head] >> 1; const p = queue[head] & 1; const t = time[queue[head]]; const visit = (v: number): void => { const s = 2 * v + (1 - p); if (time[s] === -1) { time[s] = t + 1; queue.push(s); } }; if (shelter[u] === 1) visit(u); // 쉼터에서 1분 기다린다 for (const [v, k] of bridges[u]) { // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다 if (k === 0 || (k === 1) === (p === 1)) visit(v); }}const first: number[] = [];let reached = 0;for (let v = 1; v <= n; v++) { const even = time[2 * v]; const odd = time[2 * v + 1]; // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽 const best = even === -1 ? odd : odd === -1 ? even : Math.min(even, odd); if (best !== -1) reached++; first.push(best);}console.log(reached);console.log(first.join(" "));
JavaMain.java · 67 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); st.nextToken(); int n = (int) st.nval; st.nextToken(); int m = (int) st.nval; boolean[] shelter = new boolean[n + 1]; for (int v = 1; v <= n; v++) { st.nextToken(); shelter[v] = st.nval == 1; } // bridges.get(u) = {이웃 섬, 종류}들(다리는 양쪽으로 건넌다) List<List<int[]>> bridges = new ArrayList<>(); for (int v = 0; v <= n; v++) bridges.add(new ArrayList<>()); for (int i = 0; i < m; i++) { st.nextToken(); int a = (int) st.nval; st.nextToken(); int b = (int) st.nval; st.nextToken(); int k = (int) st.nval; bridges.get(a).add(new int[] {b, k}); bridges.get(b).add(new int[] {a, k}); } // 상태 = (섬, 분의 홀짝). time[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때 int[] time = new int[2 * n + 2]; Arrays.fill(time, -1); time[2] = 0; ArrayDeque<Integer> queue = new ArrayDeque<>(); queue.add(2); while (!queue.isEmpty()) { int state = queue.poll(); int u = state / 2, p = state % 2; int t = time[state] + 1; if (shelter[u] && time[2 * u + 1 - p] == -1) { // 쉼터에서 1분 기다린다 time[2 * u + 1 - p] = t; queue.add(2 * u + 1 - p); } for (int[] bridge : bridges.get(u)) { int v = bridge[0], k = bridge[1]; // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다 boolean open = k == 0 || (k == 1) == (p == 1); if (open && time[2 * v + 1 - p] == -1) { time[2 * v + 1 - p] = t; queue.add(2 * v + 1 - p); } } } StringBuilder sb = new StringBuilder(); int reached = 0; for (int v = 1; v <= n; v++) { int even = time[2 * v], odd = time[2 * v + 1]; // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽 int best = even == -1 ? odd : odd == -1 ? even : Math.min(even, odd); if (best != -1) reached++; sb.append(best).append(v < n ? ' ' : '\n'); } System.out.print(reached + "\n" + sb); }}
C#Main.cs · 64 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), m = int.Parse(data[1]); var shelter = new bool[n + 1]; for (int v = 1; v <= n; v++) shelter[v] = data[1 + v] == "1"; // bridges[u] = (이웃 섬, 종류)들(다리는 양쪽으로 건넌다) var bridges = new List<(int To, int Kind)>[n + 1]; for (int v = 0; v <= n; v++) bridges[v] = new List<(int To, int Kind)>(); for (int i = 0; i < m; i++) { int a = int.Parse(data[2 + n + 3 * i]), b = int.Parse(data[3 + n + 3 * i]), k = int.Parse(data[4 + n + 3 * i]); bridges[a].Add((b, k)); bridges[b].Add((a, k)); } // 상태 = (섬, 분의 홀짝). time[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때 var time = new int[2 * n + 2]; Array.Fill(time, -1); time[2] = 0; var queue = new Queue<int>(); queue.Enqueue(2); while (queue.Count > 0) { int state = queue.Dequeue(); int u = state / 2, p = state % 2; int t = time[state] + 1; if (shelter[u] && time[2 * u + 1 - p] == -1) // 쉼터에서 1분 기다린다 { time[2 * u + 1 - p] = t; queue.Enqueue(2 * u + 1 - p); } foreach (var (v, k) in bridges[u]) { // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다 bool open = k == 0 || (k == 1) == (p == 1); if (open && time[2 * v + 1 - p] == -1) { time[2 * v + 1 - p] = t; queue.Enqueue(2 * v + 1 - p); } } } var sb = new StringBuilder(); int reached = 0; for (int v = 1; v <= n; v++) { int even = time[2 * v], odd = time[2 * v + 1]; // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽 int best = even == -1 ? odd : odd == -1 ? even : Math.Min(even, odd); if (best != -1) reached++; sb.Append(best).Append(v < n ? ' ' : '\n'); } Console.Write(reached + "\n" + sb); }}
C++main.cpp · 60 줄
#include <algorithm>#include <iostream>#include <queue>#include <utility>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> shelter(n + 1); for (int v = 1; v <= n; v++) cin >> shelter[v]; // bridges[u] = {이웃 섬, 종류}들(다리는 양쪽으로 건넌다) vector<vector<pair<int, int>>> bridges(n + 1); for (int i = 0; i < m; i++) { int a, b, k; cin >> a >> b >> k; bridges[a].push_back({b, k}); bridges[b].push_back({a, k}); } // 상태 = (섬, 분의 홀짝). when[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때 vector<int> when(2 * n + 2, -1); queue<int> q; when[2] = 0; q.push(2); while (!q.empty()) { int state = q.front(); q.pop(); int u = state / 2, p = state % 2; int t = when[state] + 1; if (shelter[u] && when[2 * u + 1 - p] == -1) { // 쉼터에서 1분 기다린다 when[2 * u + 1 - p] = t; q.push(2 * u + 1 - p); } for (auto [v, k] : bridges[u]) { // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다 bool open = k == 0 || (k == 1) == (p == 1); if (open && when[2 * v + 1 - p] == -1) { when[2 * v + 1 - p] = t; q.push(2 * v + 1 - p); } } } vector<int> first(n + 1); int reached = 0; for (int v = 1; v <= n; v++) { int even = when[2 * v], odd = when[2 * v + 1]; // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽 first[v] = even == -1 ? odd : odd == -1 ? even : min(even, odd); if (first[v] != -1) reached++; } cout << reached << "\n"; for (int v = 1; v <= n; v++) cout << first[v] << (v < n ? ' ' : '\n'); return 0;}
Cmain.c · 65 줄
#include <stdio.h>#include <stdlib.h>int main(void) { int n, m; if (scanf("%d %d", &n, &m) != 2) return 0; int *shelter = malloc((n + 1) * sizeof(int)); for (int v = 1; v <= n; v++) scanf("%d", &shelter[v]); // 인접 목록을 배열로: head[u]에서 시작해 next[e]로 따라가며 to[e], kind[e]를 본다 // 다리 하나가 양쪽으로 건너는 길 둘이 되므로 칸이 2m개 든다 int *head = malloc((n + 1) * sizeof(int)); int *next = malloc((2 * m + 1) * sizeof(int)); int *to = malloc((2 * m + 1) * sizeof(int)); int *kind = malloc((2 * m + 1) * sizeof(int)); for (int v = 0; v <= n; v++) head[v] = -1; for (int i = 0; i < m; i++) { int a, b, k; scanf("%d %d %d", &a, &b, &k); to[2 * i] = b; kind[2 * i] = k; next[2 * i] = head[a]; head[a] = 2 * i; to[2 * i + 1] = a; kind[2 * i + 1] = k; next[2 * i + 1] = head[b]; head[b] = 2 * i + 1; } // 상태 = (섬, 분의 홀짝). time[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때 int states = 2 * n + 2; int *time = malloc(states * sizeof(int)); int *queue = malloc(states * sizeof(int)); // 상태마다 한 번만 들어간다 for (int s = 0; s < states; s++) time[s] = -1; int qh = 0, qt = 0; time[2] = 0; queue[qt++] = 2; while (qh < qt) { int state = queue[qh++]; int u = state / 2, p = state % 2; int t = time[state] + 1; if (shelter[u] && time[2 * u + 1 - p] == -1) { // 쉼터에서 1분 기다린다 time[2 * u + 1 - p] = t; queue[qt++] = 2 * u + 1 - p; } for (int e = head[u]; e != -1; e = next[e]) { int v = to[e], k = kind[e]; // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다 int open = k == 0 || (k == 1) == (p == 1); if (open && time[2 * v + 1 - p] == -1) { time[2 * v + 1 - p] = t; queue[qt++] = 2 * v + 1 - p; } } } int reached = 0; for (int v = 1; v <= n; v++) { if (time[2 * v] != -1 || time[2 * v + 1] != -1) reached++; } printf("%d\n", reached); for (int v = 1; v <= n; v++) { int even = time[2 * v], odd = time[2 * v + 1]; // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽 int best = even == -1 ? odd : odd == -1 ? even : (even < odd ? even : odd); printf(v > 1 ? " %d" : "%d", best); } printf("\n"); free(shelter); free(head); free(next); free(to); free(kind); free(time); free(queue); return 0;}
Craykonmain.cray · 65 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1];// 목록은 10,000칸까지라 섬 번호에서 1을 빼 0번부터 둔다shelter = 콘솔.수들읽기();// bridges[u] = [이웃 섬, 종류]들(다리는 양쪽으로 건넌다)bridges = [];반복 (v = 0; v < n; v++){ bridges.넣기([]);}반복 (i = 0; i < m; i++){ 줄 = 콘솔.수들읽기(); bridges[줄[0] - 1].넣기([줄[1] - 1, 줄[2]]); bridges[줄[1] - 1].넣기([줄[0] - 1, 줄[2]]);}// 상태 = (섬, 분의 홀짝). 상태가 2n개라 목록 하나(10,000칸)에 못 담으니 홀짝마다 목록을 따로 둔다// seen[p][v] = v번 섬에 홀짝이 p인 분에 있어 본 적이 있는가seen = [새목록(n, 거짓), 새목록(n, 거짓)];first = 새목록(n, -1);seen[0][0] = 참;first[0] = 0;reached = 1;// t분에 새로 나온 상태는 홀짝이 모두 같으니, 큐 대신 '이번 분의 섬들'을 한 층씩 넘긴다frontier = [0];t = 0;동안 (frontier.개수 > 0){ p = t % 2; q = 1 - p; next = []; 각각 (u 에서 frontier) { 만약 (shelter[u] == 1 && !seen[q][u]) { seen[q][u] = 참; next.넣기(u); } 각각 (b 에서 bridges[u]) { v = b[0]; k = b[1]; // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다 open = k == 0 || k == 1 && p == 1 || k == 2 && p == 0; 만약 (open && !seen[q][v]) { seen[q][v] = 참; 만약 (first[v] == -1) { first[v] = t + 1; reached++; } next.넣기(v); } } } frontier = next; t++;}콘솔.쓰기(reached);콘솔.쓰기(first);