직사각형 지도 위에서 S 칸을 떠나 E 칸까지 가려 한다.
지도의 글자는 . 빈칸, # 벽, S 출발, E 도착, A·B·C 색 문, a·b·c 스위치다.
1분마다 위·아래·왼쪽·오른쪽으로 붙은 칸 하나로 옮긴다. 지도 밖, 벽, 닫힌 문으로는 옮길 수 없고, 제자리에 머물 수도 없다.
처음에는 모든 문이 닫혀 있다.
스위치 칸에 들어설 때마다 그 스위치와 같은 색의 문이 모두 한꺼번에 뒤집힌다(a는 A, b는 B, c는 C). 닫혀 있던 문은 열리고, 열려 있던 문은 닫힌다.
스위치 칸에서 나갈 때는 아무 일도 없다. 같은 스위치에 다시 들어서면 다시 뒤집힌다.
같은 색 스위치가 여러 개일 수 있고, 어느 것에 들어서도 똑같이 뒤집힌다.
뒤집기는 스위치 칸에 들어설 때만 일어나므로, 문 칸에 서 있는 동안 그 문이 닫히는 일은 없다.
S와 E는 빈칸처럼 지나갈 수 있고, S 칸에 다시 들어가도 된다.
E에 처음 닿는 가장 짧은 시간(분)을 출력하라. 닿을 수 없으면 -1을 출력하라.
첫 줄에 R과 C, 다음 R줄에 C글자씩 지도가 주어진다.
입력
1 ≤ R, C ≤ 30. 지도에는 S와 E가 하나씩 있고, 다른 글자는 .#ABCabc뿐이다.
출력
가장 짧은 시간 또는 -1
예시 1 · stdin
2 5
SaaAE
...##
stdout
6
예시 2 · stdin
1 5
SaaAE
stdout
6
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
같은 칸이라도 열린 문이 다르면 다른 상황이라서, 상태를 (칸, 열린 문 색의 비트마스크 0~7)로 잡고 너비 우선 탐색을 해요. 상태는 많아야 30 × 30 × 8 = 7,200개예요. 스위치를 밟으면 mask ^ (1 << 색)(XOR)으로 그 비트만 뒤집어요. 큐: Python collections.deque, JS·TS 배열에 넣고 읽을 자리 head를 옮기기(shift()는 매번 앞을 당겨서 느려요), Java ArrayDeque, C# Queue<int>, C 고정 배열과 head·tail, C++ std::queue. 크레이콘에는 비트 연산이 없어서 색마다 1·2·4를 더한 수로 담고 수학.몫(mask, 2) % 2처럼 몫과 나머지로 읽고, 켜져 있으면 빼고 꺼져 있으면 더해서 뒤집어요. 큐는 목록과 head예요. 연산자 우선순위도 언어마다 달라요: Python은 &가 ==보다 먼저라 m >> k & 1 == 0이 뜻대로 되지만, C·C++·JS는 ==가 먼저라 m >> k & (1 == 0), 곧 늘 0이 되고, Java·C#은 int와 bool을 &할 수 없어 컴파일 오류가 나요. 괄호 ((m >> k) & 1) == 0을 쓰세요. 함정 넷: ① 열쇠 문제처럼 mask | bit로 한 번 연 문을 계속 열어 두면, 다시 밟아 닫힌 문을 지나가 버려요. ② 방문 표시를 칸마다 하나만 두면, 문 상태를 바꾸러 같은 칸에 다시 와야 하는 길(예시)을 놓쳐요. ③ 위의 C 우선순위 실수로 문이 늘 열린 것으로 보여요. ④ 스위치를 밟을 때 지도 하나를 직접 고치면(문 글자를 .으로), 큐에 있는 다른 상태들까지 그 문이 열린 지도를 보게 돼요. 문 상태는 지도가 아니라 상태 안에 담아야 해요.
Pythonmain.py · 42 줄
import sysfrom collections import dequedef main(): data = sys.stdin.read().split() r, c = int(data[0]), int(data[1]) grid = data[2:2 + r] for y in range(r): for x in range(c): if grid[y][x] == "S": start = (y, x) # 상태 = (칸, 열린 문 색의 비트마스크). 같은 칸이라도 열린 문이 다르면 다른 상태다 dist = [[[-1] * 8 for _ in range(c)] for _ in range(r)] sy, sx = start dist[sy][sx][0] = 0 queue = deque([(sy, sx, 0)]) while queue: y, x, mask = queue.popleft() d = dist[y][x][mask] for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)): ny, nx = y + dy, x + dx if not (0 <= ny < r and 0 <= nx < c): continue ch = grid[ny][nx] if ch == "#": continue if ch in "ABC" and not mask >> (ord(ch) - ord("A")) & 1: continue # 닫힌 문 nmask = mask if ch in "abc": nmask = mask ^ (1 << (ord(ch) - ord("a"))) # 들어설 때마다 뒤집는다 if ch == "E": print(d + 1) return if dist[ny][nx][nmask] < 0: dist[ny][nx][nmask] = d + 1 queue.append((ny, nx, nmask)) print(-1)main()
JavaScriptmain.js · 40 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const r = Number(data[0]);const c = Number(data[1]);const grid = data.slice(2, 2 + r);let start = 0;for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "S") start = y * c + x;// 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크const dist = new Array(r * c * 8).fill(-1);const queue = [start * 8];dist[start * 8] = 0;const DY = [-1, 1, 0, 0];const DX = [0, 0, -1, 1];let answer = -1;search: for (let head = 0; head < queue.length; head++) { const s = queue[head]; const cell = s >> 3; const mask = s & 7; const y = Math.floor(cell / c); const x = cell % c; for (let k = 0; k < 4; k++) { const ny = y + DY[k]; const nx = x + DX[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; const ch = grid[ny][nx]; if (ch === "#") continue; if (ch >= "A" && ch <= "C" && ((mask >> (ch.charCodeAt(0) - 65)) & 1) === 0) continue; // 닫힌 문 let nmask = mask; if (ch >= "a" && ch <= "c") nmask ^= 1 << (ch.charCodeAt(0) - 97); // 들어설 때마다 뒤집는다 if (ch === "E") { answer = dist[s] + 1; break search; } const ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.push(ns); } }}console.log(answer);
TypeScriptmain.ts · 40 줄
const data: string[] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const r = Number(data[0]);const c = Number(data[1]);const grid = data.slice(2, 2 + r);let start = 0;for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "S") start = y * c + x;// 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크const dist: number[] = new Array(r * c * 8).fill(-1);const queue: number[] = [start * 8];dist[start * 8] = 0;const DY = [-1, 1, 0, 0];const DX = [0, 0, -1, 1];let answer = -1;search: for (let head = 0; head < queue.length; head++) { const s = queue[head]; const cell = s >> 3; const mask = s & 7; const y = Math.floor(cell / c); const x = cell % c; for (let k = 0; k < 4; k++) { const ny = y + DY[k]; const nx = x + DX[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; const ch = grid[ny][nx]; if (ch === "#") continue; if (ch >= "A" && ch <= "C" && ((mask >> (ch.charCodeAt(0) - 65)) & 1) === 0) continue; // 닫힌 문 let nmask = mask; if (ch >= "a" && ch <= "c") nmask ^= 1 << (ch.charCodeAt(0) - 97); // 들어설 때마다 뒤집는다 if (ch === "E") { answer = dist[s] + 1; break search; } const ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.push(ns); } }}console.log(answer);
JavaMain.java · 48 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int r = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); char[][] grid = new char[r][]; int start = 0; for (int y = 0; y < r; y++) { grid[y] = br.readLine().trim().toCharArray(); for (int x = 0; x < c; x++) if (grid[y][x] == 'S') start = y * c + x; } // 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크 int[] dist = new int[r * c * 8]; Arrays.fill(dist, -1); ArrayDeque<Integer> queue = new ArrayDeque<>(); dist[start * 8] = 0; queue.add(start * 8); int[] dy = {-1, 1, 0, 0}, dx = {0, 0, -1, 1}; while (!queue.isEmpty()) { int s = queue.poll(); int cell = s / 8, mask = s % 8; int y = cell / c, x = cell % c; for (int k = 0; k < 4; k++) { int ny = y + dy[k], nx = x + dx[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; char ch = grid[ny][nx]; if (ch == '#') continue; if (ch >= 'A' && ch <= 'C' && ((mask >> (ch - 'A')) & 1) == 0) continue; // 닫힌 문 int nmask = mask; if (ch >= 'a' && ch <= 'c') nmask ^= 1 << (ch - 'a'); // 들어설 때마다 뒤집는다 if (ch == 'E') { System.out.println(dist[s] + 1); return; } int ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.add(ns); } } } System.out.println(-1); }}
C#Main.cs · 53 줄
using System;using System.Collections.Generic;class Program{ static void Main() { var first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int r = int.Parse(first[0]), c = int.Parse(first[1]); var grid = new string[r]; int start = 0; for (int y = 0; y < r; y++) { grid[y] = Console.ReadLine().Trim(); for (int x = 0; x < c; x++) if (grid[y][x] == 'S') start = y * c + x; } // 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크 var dist = new int[r * c * 8]; Array.Fill(dist, -1); var queue = new Queue<int>(); dist[start * 8] = 0; queue.Enqueue(start * 8); int[] dy = { -1, 1, 0, 0 }, dx = { 0, 0, -1, 1 }; while (queue.Count > 0) { int s = queue.Dequeue(); int cell = s / 8, mask = s % 8; int y = cell / c, x = cell % c; for (int k = 0; k < 4; k++) { int ny = y + dy[k], nx = x + dx[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; char ch = grid[ny][nx]; if (ch == '#') continue; if (ch >= 'A' && ch <= 'C' && ((mask >> (ch - 'A')) & 1) == 0) continue; // 닫힌 문 int nmask = mask; if (ch >= 'a' && ch <= 'c') nmask ^= 1 << (ch - 'a'); // 들어설 때마다 뒤집는다 if (ch == 'E') { Console.WriteLine(dist[s] + 1); return; } int ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.Enqueue(ns); } } } Console.WriteLine(-1); }}
C++main.cpp · 48 줄
#include <iostream>#include <queue>#include <string>#include <vector>int main() { int r, c; std::cin >> r >> c; std::vector<std::string> grid(r); int start = 0; for (int y = 0; y < r; y++) { std::cin >> grid[y]; for (int x = 0; x < c; x++) if (grid[y][x] == 'S') start = y * c + x; } // 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크 std::vector<int> dist(r * c * 8, -1); std::queue<int> q; dist[start * 8] = 0; q.push(start * 8); const int dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1}; while (!q.empty()) { int s = q.front(); q.pop(); int cell = s / 8, mask = s % 8; int y = cell / c, x = cell % c; for (int k = 0; k < 4; k++) { int ny = y + dy[k], nx = x + dx[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; char ch = grid[ny][nx]; if (ch == '#') continue; if (ch >= 'A' && ch <= 'C' && ((mask >> (ch - 'A')) & 1) == 0) continue; // 닫힌 문 int nmask = mask; if (ch >= 'a' && ch <= 'c') nmask ^= 1 << (ch - 'a'); // 들어설 때마다 뒤집는다 if (ch == 'E') { std::cout << dist[s] + 1 << '\n'; return 0; } int ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; q.push(ns); } } } std::cout << -1 << '\n'; return 0;}
Cmain.c · 46 줄
#include <stdio.h>static char grid[30][32];static int dist[30 * 30 * 8];static int queue[30 * 30 * 8]; /* 상태마다 많아야 한 번 들어간다 */int main(void) { int r, c, start = 0; scanf("%d %d", &r, &c); for (int y = 0; y < r; y++) { scanf("%31s", grid[y]); for (int x = 0; x < c; x++) if (grid[y][x] == 'S') start = y * c + x; } /* 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크 */ for (int i = 0; i < r * c * 8; i++) dist[i] = -1; int head = 0, tail = 0; dist[start * 8] = 0; queue[tail++] = start * 8; const int dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1}; while (head < tail) { int s = queue[head++]; int cell = s / 8, mask = s % 8; int y = cell / c, x = cell % c; for (int k = 0; k < 4; k++) { int ny = y + dy[k], nx = x + dx[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; char ch = grid[ny][nx]; if (ch == '#') continue; if (ch >= 'A' && ch <= 'C' && ((mask >> (ch - 'A')) & 1) == 0) continue; /* 닫힌 문 */ int nmask = mask; if (ch >= 'a' && ch <= 'c') nmask ^= 1 << (ch - 'a'); /* 들어설 때마다 뒤집는다 */ if (ch == 'E') { printf("%d\n", dist[s] + 1); return 0; } int ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue[tail++] = ns; } } } printf("-1\n"); return 0;}
Craykonmain.cray · 88 줄
// 크레이콘에는 비트 연산이 없어서, 열린 문 색 세 개를 0~7의 수(1·2·4의 합)로 담고 몫과 나머지로 읽는다첫줄 = 콘솔.수들읽기();r = 첫줄[0];c = 첫줄[1];grid = [];start = 0;반복 (y = 0; y < r; y++){ 줄 = 콘솔.줄읽기().공백제거(); grid.넣기(줄); 반복 (x = 0; x < c; x++) { 만약 (줄[x] == "S") { start = y * c + x; } }}문색 = 사전(); // 문 글자 → 그 색의 값(1, 2, 4)문색["A"] = 1;문색["B"] = 2;문색["C"] = 4;스위치색 = 사전();스위치색["a"] = 1;스위치색["b"] = 2;스위치색["c"] = 4;// 상태 번호 = 칸 * 8 + 열린 문 색의 합dist = 새목록(r * c * 8, -1);queue = [start * 8];dist[start * 8] = 0;DY = [-1, 1, 0, 0];DX = [0, 0, -1, 1];answer = -1;head = 0;동안 (head < queue.개수 && answer < 0){ s = queue[head]; head++; cell = 수학.몫(s, 8); mask = s % 8; y = 수학.몫(cell, c); x = cell % c; 반복 (k = 0; k < 4; k++) { ny = y + DY[k]; nx = x + DX[k]; 만약 (ny < 0 || ny >= r || nx < 0 || nx >= c) { 건너뛰기; } ch = grid[ny][nx]; 만약 (ch == "#") { 건너뛰기; } 만약 (문색.있나(ch) && 수학.몫(mask, 문색[ch]) % 2 == 0) { 건너뛰기; // 닫힌 문 } nmask = mask; 만약 (스위치색.있나(ch)) { v = 스위치색[ch]; // 들어설 때마다 뒤집는다: 켜져 있으면 빼고, 꺼져 있으면 더한다 만약 (수학.몫(mask, v) % 2 == 1) { nmask = mask - v; } 아니면 { nmask = mask + v; } } 만약 (ch == "E") { answer = dist[s] + 1; 그만; } ns = (ny * c + nx) * 8 + nmask; 만약 (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.넣기(ns); } }}콘솔.쓰기(answer);