벽에 타일이 R줄로, 한 줄에 C장씩 붙어 있다.
타일은 짙은 타일(#) 아니면 옅은 타일(.)인데, 몇 장은 가려져 있어 색을 모른다(?).
위아래로 이웃한 두 줄과 좌우로 이웃한 두 칸이 만나는 곳마다 타일 네 장이 한 점에서 만나고, 그 점에 숫자가 하나 적혀 있다.
숫자는 그 점에서 만나는 타일 네 장 가운데 짙은 타일의 수다.
가려진 타일마다 색을 정해서 모든 숫자가 맞게 하려고 한다. 보이는 타일의 색은 바꿀 수 없다.
첫 줄에 R과 C가 주어진다.
다음 R줄에 벽이 한 줄에 C글자씩 주어진다.
다음 R - 1줄에 숫자가 한 줄에 C - 1개씩 주어진다. 이 가운데 i번째 줄의 j번째 숫자는 벽의 i번째 줄과 i + 1번째 줄, j번째 칸과 j + 1번째 칸에 있는 타일 네 장이 만나는 점의 숫자다.
먼저 색을 정하는 방법이 모두 몇 가지인지 출력한다.
방법이 하나라도 있으면, 그렇게 만들 수 있는 벽 가운데 가장 앞선 벽도 출력한다.
두 벽을 첫 줄부터 차례로, 줄 안에서는 왼쪽 타일부터 견주어 처음으로 색이 다른 자리에서 옅은 타일을 가진 벽이 앞선 벽이다.
입력
2 ≤ R, C ≤ 10. 벽의 글자는 #, ., ? 가운데 하나이고 글자 사이에 빈칸이 없다. 숫자는 0 이상 4 이하의 정수이고 빈칸 하나로 띄워 주어진다
출력
첫 줄에 방법의 수. 방법이 있으면 이어서 R줄에 가장 앞선 벽(#과 .만으로)
예시 1 · stdin
3 4
???.
?#.?
????
2 2 2
2 2 2
stdout
3
..#.
##.#
..#.
예시 2 · stdin
2 2
#?
?.
4
stdout
0
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
가려진 타일을 하나하나 다 정해 본 뒤에 숫자를 확인하면 타일이 100장일 때 2^100가지라서 끝나지 않아요. 하지만 어느 줄의 첫 타일까지 정해지면 그 줄의 나머지 타일은 고를 것이 없어요. 왼쪽 위 점의 숫자에서 이미 정해진 세 타일을 빼면 그 타일이 나오니까요. 그래서 골라 보는 것은 첫 줄의 타일 C장과 둘째 줄부터의 첫 타일 R - 1장뿐이에요. 많아야 2^19가지이고, 숫자에 어긋나는 순간 그 갈래를 버리니 훨씬 적어요. 풀이는 모두 재귀 함수로 첫 줄을 한 장씩 고른 다음, 줄마다 첫 타일을 고르고 나머지를 채워요. 옅은 타일을 먼저 해 보기 때문에 처음 찾은 벽이 가장 앞선 벽이에요. 고르는 중인 벽은 Python은 리스트의 리스트, JS·TS는 배열의 배열, Java는 int[][], C#은 int[,], C는 int grid[10][10], C++은 std::vector<std::vector<int>>, 크레이콘은 새목록(줄수, 새목록(칸수, 0))에 두어요. 방법의 수를 세는 변수는 Python에서는 안쪽 함수가 바꾸려면 nonlocal이 필요해요. TS는 함수 안에서 바뀐 best를 처음 넣은 null로만 알고 있어서 if (best !== null) 안에서 never로 보고 타입 오류(TS2488)를 내요. 그래서 best as string[] | null로 타입을 다시 알려 줘요. 함정 하나: 맞는 벽을 문자열로 모아 가장 작은 것을 고르면 안 돼요. 문자 코드로는 #(35)이 .(46)보다 앞이라서 첫째 예시에서 #.#.으로 시작하는 벽이 뽑혀요. 함정 둘: 숫자로 정해진 타일도 이미 보이는 타일과 같아야 해요. 확인하지 않으면 첫째 예시의 방법이 3이 아니라 11이 돼요. 함정 셋: 숫자에서 빼고 남은 값이 0이나 1이어야 해요. 음수만 걸러내고 1보다 큰 값을 그냥 두면 첫째 예시가 4가 돼요. 함정 넷: 첫 줄만 정한다고 다 정해지지 않아요. 둘째 줄부터도 첫 타일은 골라야 해요. 옅은 타일로만 두면 첫째 예시가 1이 돼요. 함정 다섯: 크레이콘에서 가려진 타일을 하나하나 다 정해 보면 큰 벽에서 '너무 오래 걸려서'라는 말과 함께 멈춰요.
Pythonmain.py · 58 줄
import sysdef main(): data = sys.stdin.read().split() rows, cols = int(data[0]), int(data[1]) # known[i][j]: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?) known = [[-1 if ch == "?" else int(ch == "#") for ch in data[2 + i]] for i in range(rows)] pos = 2 + rows hints = [[int(data[pos + i * (cols - 1) + j]) for j in range(cols - 1)] for i in range(rows - 1)] grid = [[0] * cols for _ in range(rows)] count = 0 best = None def fill_rest(i): """줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 False""" for j in range(1, cols): v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1] if v < 0 or v > 1: # 타일은 짙거나 옅을 뿐이다 return False if known[i][j] != -1 and known[i][j] != v: # 이미 보이는 타일과 달라도 안 된다 return False grid[i][j] = v return True def later_rows(i): nonlocal count, best if i == rows: count += 1 if best is None: # 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 best = ["".join(".#"[v] for v in row) for row in grid] return for v in (0, 1): # 둘째 줄부터는 첫 타일만 고른다 if known[i][0] != -1 and known[i][0] != v: continue grid[i][0] = v if fill_rest(i): later_rows(i + 1) def first_row(j): if j == cols: later_rows(1) return for v in (0, 1): # 첫 줄은 타일마다 고른다 if known[0][j] != -1 and known[0][j] != v: continue grid[0][j] = v first_row(j + 1) first_row(0) out = [str(count)] if best is not None: out += best print("\n".join(out))main()
JavaScriptmain.js · 59 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean);const rows = Number(data[0]), cols = Number(data[1]);// known[i][j]: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?)const known = [];for (let i = 0; i < rows; i++) { known.push([...data[2 + i]].map((ch) => (ch === "?" ? -1 : ch === "#" ? 1 : 0)));}const hints = [];let pos = 2 + rows;for (let i = 0; i < rows - 1; i++) { hints.push(data.slice(pos, pos + cols - 1).map(Number)); pos += cols - 1;}const grid = known.map((row) => row.map(() => 0));let count = 0;let best = null;// 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 falsefunction fillRest(i) { for (let j = 1; j < cols; j++) { const v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1]; if (v < 0 || v > 1) return false; // 타일은 짙거나 옅을 뿐이다 if (known[i][j] !== -1 && known[i][j] !== v) return false; // 이미 보이는 타일과 달라도 안 된다 grid[i][j] = v; } return true;}function laterRows(i) { if (i === rows) { count++; // 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 if (best === null) best = grid.map((row) => row.map((v) => ".#"[v]).join("")); return; } for (let v = 0; v <= 1; v++) { // 둘째 줄부터는 첫 타일만 고른다 if (known[i][0] !== -1 && known[i][0] !== v) continue; grid[i][0] = v; if (fillRest(i)) laterRows(i + 1); }}function firstRow(j) { if (j === cols) { laterRows(1); return; } for (let v = 0; v <= 1; v++) { // 첫 줄은 타일마다 고른다 if (known[0][j] !== -1 && known[0][j] !== v) continue; grid[0][j] = v; firstRow(j + 1); }}firstRow(0);const out = [String(count)];if (best !== null) out.push(...best);console.log(out.join("\n"));
TypeScriptmain.ts · 62 줄
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").split(/\s+/).filter(Boolean);const rows = Number(data[0]), cols = Number(data[1]);// known[i][j]: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?)const known: number[][] = [];for (let i = 0; i < rows; i++) { known.push([...data[2 + i]].map((ch) => (ch === "?" ? -1 : ch === "#" ? 1 : 0)));}const hints: number[][] = [];let pos = 2 + rows;for (let i = 0; i < rows - 1; i++) { hints.push(data.slice(pos, pos + cols - 1).map(Number)); pos += cols - 1;}const grid: number[][] = known.map((row) => row.map(() => 0));let count = 0;let best: string[] | null = null;// 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 falsefunction fillRest(i: number): boolean { for (let j = 1; j < cols; j++) { const v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1]; if (v < 0 || v > 1) return false; // 타일은 짙거나 옅을 뿐이다 if (known[i][j] !== -1 && known[i][j] !== v) return false; // 이미 보이는 타일과 달라도 안 된다 grid[i][j] = v; } return true;}function laterRows(i: number): void { if (i === rows) { count++; // 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 if (best === null) best = grid.map((row) => row.map((v) => ".#"[v]).join("")); return; } for (let v = 0; v <= 1; v++) { // 둘째 줄부터는 첫 타일만 고른다 if (known[i][0] !== -1 && known[i][0] !== v) continue; grid[i][0] = v; if (fillRest(i)) laterRows(i + 1); }}function firstRow(j: number): void { if (j === cols) { laterRows(1); return; } for (let v = 0; v <= 1; v++) { // 첫 줄은 타일마다 고른다 if (known[0][j] !== -1 && known[0][j] !== v) continue; grid[0][j] = v; firstRow(j + 1); }}firstRow(0);const out: string[] = [String(count)];// 함수 안에서 바꾼 best를 TS는 여전히 null로만 알고 있어서, 타입을 다시 알려 준다const found = best as string[] | null;if (found !== null) out.push(...found);console.log(out.join("\n"));
JavaMain.java · 75 줄
import java.io.*;import java.util.*;public class Main { static int rows, cols, count = 0; static int[][] known, hints, grid; // known: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?) static String[] best = null; // 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 false static boolean fillRest(int i) { for (int j = 1; j < cols; j++) { int v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1]; if (v < 0 || v > 1) return false; // 타일은 짙거나 옅을 뿐이다 if (known[i][j] != -1 && known[i][j] != v) return false; // 이미 보이는 타일과 달라도 안 된다 grid[i][j] = v; } return true; } static void laterRows(int i) { if (i == rows) { count++; if (best == null) { // 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 best = new String[rows]; for (int r = 0; r < rows; r++) { StringBuilder sb = new StringBuilder(); for (int c = 0; c < cols; c++) sb.append(grid[r][c] == 1 ? '#' : '.'); best[r] = sb.toString(); } } return; } for (int v = 0; v <= 1; v++) { // 둘째 줄부터는 첫 타일만 고른다 if (known[i][0] != -1 && known[i][0] != v) continue; grid[i][0] = v; if (fillRest(i)) laterRows(i + 1); } } static void firstRow(int j) { if (j == cols) { laterRows(1); return; } for (int v = 0; v <= 1; v++) { // 첫 줄은 타일마다 고른다 if (known[0][j] != -1 && known[0][j] != v) continue; grid[0][j] = v; firstRow(j + 1); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); rows = in.nextInt(); cols = in.nextInt(); known = new int[rows][cols]; grid = new int[rows][cols]; for (int i = 0; i < rows; i++) { String line = in.next(); for (int j = 0; j < cols; j++) { char ch = line.charAt(j); known[i][j] = ch == '?' ? -1 : ch == '#' ? 1 : 0; } } hints = new int[rows - 1][cols - 1]; for (int i = 0; i < rows - 1; i++) for (int j = 0; j < cols - 1; j++) hints[i][j] = in.nextInt(); firstRow(0); StringBuilder out = new StringBuilder(); out.append(count).append('\n'); if (best != null) for (String line : best) out.append(line).append('\n'); System.out.print(out); }}
C#Main.cs · 87 줄
using System;using System.Text;class Program{ static int rows, cols, count = 0; static int[,] known, hints, grid; // known: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?) static string[] best = null; // 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 false static bool FillRest(int i) { for (int j = 1; j < cols; j++) { int v = hints[i - 1, j - 1] - grid[i - 1, j - 1] - grid[i - 1, j] - grid[i, j - 1]; if (v < 0 || v > 1) return false; // 타일은 짙거나 옅을 뿐이다 if (known[i, j] != -1 && known[i, j] != v) return false; // 이미 보이는 타일과 달라도 안 된다 grid[i, j] = v; } return true; } static void LaterRows(int i) { if (i == rows) { count++; if (best == null) // 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 { best = new string[rows]; for (int r = 0; r < rows; r++) { var sb = new StringBuilder(); for (int c = 0; c < cols; c++) sb.Append(grid[r, c] == 1 ? '#' : '.'); best[r] = sb.ToString(); } } return; } for (int v = 0; v <= 1; v++) // 둘째 줄부터는 첫 타일만 고른다 { if (known[i, 0] != -1 && known[i, 0] != v) continue; grid[i, 0] = v; if (FillRest(i)) LaterRows(i + 1); } } static void FirstRow(int j) { if (j == cols) { LaterRows(1); return; } for (int v = 0; v <= 1; v++) // 첫 줄은 타일마다 고른다 { if (known[0, j] != -1 && known[0, j] != v) continue; grid[0, j] = v; FirstRow(j + 1); } } static void Main() { string[] tokens = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); rows = int.Parse(tokens[0]); cols = int.Parse(tokens[1]); known = new int[rows, cols]; grid = new int[rows, cols]; for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) { char ch = tokens[2 + i][j]; known[i, j] = ch == '?' ? -1 : ch == '#' ? 1 : 0; } hints = new int[rows - 1, cols - 1]; int pos = 2 + rows; for (int i = 0; i < rows - 1; i++) for (int j = 0; j < cols - 1; j++) hints[i, j] = int.Parse(tokens[pos++]); FirstRow(0); var output = new StringBuilder(); output.Append(count).Append('\n'); if (best != null) foreach (string line in best) output.Append(line).Append('\n'); Console.Write(output); }}
C++main.cpp · 67 줄
#include <iostream>#include <string>#include <vector>int rows, cols, count = 0;std::vector<std::vector<int>> known, hints, grid; // known: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?)std::vector<std::string> best;// 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 falsebool fillRest(int i) { for (int j = 1; j < cols; j++) { int v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1]; if (v < 0 || v > 1) return false; // 타일은 짙거나 옅을 뿐이다 if (known[i][j] != -1 && known[i][j] != v) return false; // 이미 보이는 타일과 달라도 안 된다 grid[i][j] = v; } return true;}void laterRows(int i) { if (i == rows) { count++; if (best.empty()) { // 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 for (const auto& row : grid) { std::string line; for (int v : row) line += v ? '#' : '.'; best.push_back(line); } } return; } for (int v = 0; v <= 1; v++) { // 둘째 줄부터는 첫 타일만 고른다 if (known[i][0] != -1 && known[i][0] != v) continue; grid[i][0] = v; if (fillRest(i)) laterRows(i + 1); }}void firstRow(int j) { if (j == cols) { laterRows(1); return; } for (int v = 0; v <= 1; v++) { // 첫 줄은 타일마다 고른다 if (known[0][j] != -1 && known[0][j] != v) continue; grid[0][j] = v; firstRow(j + 1); }}int main() { std::cin >> rows >> cols; known.assign(rows, std::vector<int>(cols)); grid.assign(rows, std::vector<int>(cols, 0)); for (int i = 0; i < rows; i++) { std::string line; std::cin >> line; for (int j = 0; j < cols; j++) known[i][j] = line[j] == '?' ? -1 : line[j] == '#' ? 1 : 0; } hints.assign(rows - 1, std::vector<int>(cols - 1)); for (auto& row : hints) for (int& h : row) std::cin >> h; firstRow(0); std::cout << count << '\n'; for (const auto& line : best) std::cout << line << '\n';}
Cmain.c · 69 줄
#include <stdio.h>#include <string.h>#define MAX 10static int rows, cols, count = 0, found = 0;static int known[MAX][MAX]; /* 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?) */static int hints[MAX][MAX], grid[MAX][MAX], best[MAX][MAX];/* 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 0 */static int fill_rest(int i) { for (int j = 1; j < cols; j++) { int v = hints[i - 1][j - 1] - grid[i - 1][j - 1] - grid[i - 1][j] - grid[i][j - 1]; if (v < 0 || v > 1) return 0; /* 타일은 짙거나 옅을 뿐이다 */ if (known[i][j] != -1 && known[i][j] != v) return 0; /* 이미 보이는 타일과 달라도 안 된다 */ grid[i][j] = v; } return 1;}static void later_rows(int i) { if (i == rows) { count++; if (!found) { /* 옅은 타일부터 해 보았으니 처음 찾은 벽이 가장 앞선다 */ found = 1; memcpy(best, grid, sizeof grid); } return; } for (int v = 0; v <= 1; v++) { /* 둘째 줄부터는 첫 타일만 고른다 */ if (known[i][0] != -1 && known[i][0] != v) continue; grid[i][0] = v; if (fill_rest(i)) later_rows(i + 1); }}static void first_row(int j) { if (j == cols) { later_rows(1); return; } for (int v = 0; v <= 1; v++) { /* 첫 줄은 타일마다 고른다 */ if (known[0][j] != -1 && known[0][j] != v) continue; grid[0][j] = v; first_row(j + 1); }}int main(void) { char line[MAX + 2]; if (scanf("%d %d", &rows, &cols) != 2) return 0; for (int i = 0; i < rows; i++) { if (scanf("%11s", line) != 1) return 0; for (int j = 0; j < cols; j++) known[i][j] = line[j] == '?' ? -1 : line[j] == '#' ? 1 : 0; } for (int i = 0; i < rows - 1; i++) for (int j = 0; j < cols - 1; j++) if (scanf("%d", &hints[i][j]) != 1) return 0; first_row(0); printf("%d\n", count); if (found) { for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) putchar(best[i][j] ? '#' : '.'); putchar('\n'); } } return 0;}
Craykonmain.cray · 116 줄
// 줄 i의 첫 타일이 정해지면 나머지 타일은 위쪽 숫자가 정해 준다. 맞지 않으면 거짓나머지채우기(i){ 반복 (j = 1; j < 칸수; j++) { v = 숫자[i - 1][j - 1] - 벽[i - 1][j - 1] - 벽[i - 1][j] - 벽[i][j - 1]; 만약 (v < 0 || v > 1) { 돌려주기 거짓; } 만약 (보임[i][j] != -1 && 보임[i][j] != v) { 돌려주기 거짓; } 벽[i][j] = v; } 돌려주기 참;}아랫줄들(i){ 만약 (i == 줄수) { 방법 += 1; 만약 (앞선벽.개수 == 0) { 각각 (줄 에서 벽) { 글 = ""; 각각 (v 에서 줄) { 만약 (v == 1) { 글 = 글 + "#"; } 아니면 { 글 = 글 + "."; } } 앞선벽.넣기(글); } } 돌려주기; } 반복 (v = 0; v <= 1; v++) { 만약 (보임[i][0] == -1 || 보임[i][0] == v) { 벽[i][0] = v; 만약 (나머지채우기(i)) { 아랫줄들(i + 1); } } }}첫줄(j){ 만약 (j == 칸수) { 아랫줄들(1); 돌려주기; } 반복 (v = 0; v <= 1; v++) { 만약 (보임[0][j] == -1 || 보임[0][j] == v) { 벽[0][j] = v; 첫줄(j + 1); } }}크기 = 콘솔.수들읽기();줄수 = 크기[0];칸수 = 크기[1];// 보임: 1 = 짙은 타일(#), 0 = 옅은 타일(.), -1 = 모르는 타일(?)보임 = [];반복 (i = 0; i < 줄수; i++){ 글자들 = 콘솔.줄읽기().공백제거(); 한줄 = []; 반복 (j = 0; j < 칸수; j++) { 만약 (글자들[j] == "?") { 한줄.넣기(-1); } 아니면 만약 (글자들[j] == "#") { 한줄.넣기(1); } 아니면 { 한줄.넣기(0); } } 보임.넣기(한줄);}숫자 = [];반복 (i = 0; i < 줄수 - 1; i++){ 숫자.넣기(콘솔.수들읽기());}벽 = 새목록(줄수, 새목록(칸수, 0));방법 = 0;앞선벽 = [];첫줄(0);콘솔.쓰기(방법);각각 (글 에서 앞선벽){ 콘솔.쓰기(글);}