열쇠 있나사전 찾기그대로 따라 하기P0364

끝없는 판에 전선 놓기

끝없이 넓은 모눈 판에 전선을 놓는다. 칸은 정수 좌표 (x, y)로 가리키고, 처음에는 모든 칸이 비어 있다. 첫 줄에 명령 수 q가, 다음 q줄에 명령이 한 줄에 하나씩 주어진다. "lay x y 길"은 칸 (x, y)에서 시작해서 길의 글자를 앞에서부터 따라 한 칸씩 움직이며 전선 하나를 놓는 명령이다. 글자 U는 y가 1 커지는 칸으로, D는 y가 1 작아지는 칸으로, L은 x가 1 작아지는 칸으로, R은 x가 1 커지는 칸으로 움직인다. 전선은 시작 칸과 움직여서 닿은 모든 칸을 차지한다. 전선이 자기가 이미 지난 칸을 다시 지나도 되고, 그런 칸은 한 번만 센다. 지나는 칸 가운데 다른 전선이 차지한 칸이 하나라도 있으면 이 전선은 놓지 못한다. 이때는 "blocked 번호"를 출력하고, 번호는 시작 칸부터 길 순서로 보았을 때 처음 만나는 차지된 칸의 전선 번호이다. 놓지 못한 전선은 판에 한 칸도 남기지 않는다. 막히지 않았으면 전선이 놓이고, 그 전선이 차지한 칸 수를 "ok 칸수"로 출력한다. 놓인 전선은 놓인 순서대로 1, 2, 3, … 번호를 받고, 놓지 못한 전선은 번호를 받지 않는다. "cut x y"는 칸 (x, y)를 차지한 전선을 통째로 걷어 내는 명령이다. 그런 전선이 있으면 그 전선이 차지한 모든 칸이 비고 "removed 번호"를 출력하며, 없으면 "none"을 출력한다. 걷어 낸 전선의 번호는 다시 쓰지 않는다. 모든 명령을 처리한 뒤 마지막 줄에 판에 남은 전선 수와 차지된 칸 수를 빈칸 하나로 띄워 출력하라.

입력: 1 ≤ q ≤ 2,000.
명령의 x, y는 −1,000,000,000 이상 1,000,000,000 이하의 정수이고 음수는 앞에 -가 붙는다.
길은 U, D, L, R로 된 1 ~ 100글자.
어느 때든 차지된 칸은 9,000개 이하
출력: 명령마다 한 줄(ok 칸수, blocked 번호, removed 번호, none), 마지막 줄에 남은 전선 수와 차지된 칸 수

예시 1 · stdin

9
lay 0 0 RRU
lay 1 -1 UU
lay 5 5 RULDR
cut 2 1
cut 2 1
lay 1 -1 UU
cut 0 -1
lay 12 3 R
lay 1 23 R

stdout

ok 4
blocked 1
ok 4
removed 1
none
ok 3
none
ok 2
ok 2
4 11

예시 2 · stdin

5
lay 1000000000 1000000000 L
lay 1000000000 999999999 L
lay 999999997 999999999 RRUL
cut 999999999 999999999
cut -1000000000 -1000000000

stdout

ok 2
ok 2
blocked 2
removed 2
none
1 2

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

'이 칸을 누가 차지했나'를 칸 → 전선 번호 사전에 열쇠가 있는지로 묻는 문제예요.
좌표가 ±10억이라 2차원 배열은 만들 수 없어요.
열쇠가 좌표 두 개라는 점에서 언어가 갈려요.
Python은 튜플 (x, y)를 그대로 열쇠로 쓰고 (x, y) in owner로 물어요.
C#은 값 튜플 Dictionary<(int, int), int>에 ContainsKey·TryGetValue, C++은 std::map<std::pair<int, int>, int>에 find를 써요(std::unordered_map은 pair의 해시가 없어서 그대로는 컴파일되지 않아요).
JS·TS의 Map은 배열도 열쇠로 받지만 내용이 아니라 같은 배열인지만 봐요.
Java는 long 하나로 묶은 HashMap<Long, Integer>와 containsKey·get, 크레이콘은 사전()에 "" + x + "," + y 문자열을 열쇠로 쓰고 owner.있나(key)로 물어요.
C는 사전이 없어서 해시 표를 직접 만들고, 지운 자리에는 표시를 남겨 그 뒤의 칸을 계속 찾을 수 있게 해요.
함정 하나: JS map.has([1, 2])는 방금 넣은 [1, 2]와 다른 배열이라 늘 false예요.
첫 예시의 둘째 명령이 막히지 않아요.
x + "," + y 같은 문자열을 열쇠로 써요.
함정 둘: 문자열로 만들 때 사이에 구분 글자가 없으면 (1, 23)과 (12, 3)이 둘 다 "123"이에요(첫 예시의 마지막 두 명령).
함정 셋: 수 하나로 묶을 때 JS x * 4000000000 + y는 4 × 10^18까지 가서 2^53을 넘고, 이웃한 칸이 같은 수가 돼요(둘째 예시의 둘째 명령).
Java ((long) x << 32) | y는 y가 음수이면 위쪽 32비트가 모두 1이 되어 x가 사라져서 (0, −1)과 (1, −1)이 같은 열쇠예요(첫 예시의 cut 0 -1).
y & 0xFFFFFFFFL로 아래 32비트만 남겨요.
함정 넷: 막힌 전선은 한 칸도 놓이지 않아요.
한 칸씩 놓으면서 검사하면 막히기 전에 놓은 칸이 남아서, 첫 예시의 여섯째 명령이 그 칸에 막혀요.
길 전체를 먼저 검사하고 나서 놓아요.
함정 다섯: 자기 길을 다시 지나는 칸은 막힌 것이 아니고 한 번만 세요.
RULDR은 6칸이 아니라 4칸이에요.
함정 여섯: 자를 때는 열쇠를 지워요.
Python del owner[cell], JS·TS delete(key), Java remove, C# Remove, C++ erase, 크레이콘 빼기예요.
값만 0으로 바꾸면 '열쇠가 있나'는 여전히 참이라 빈 칸이 차지된 것처럼 보여요.
함정 일곱: blocked의 번호는 길 순서로 처음 만난 칸의 전선이지, 막은 전선 가운데 번호가 가장 작은 것이 아니에요(둘째 예시의 셋째 명령).

Pythonmain.py · 44 줄

import sys STEP = {"U": (0, 1), "D": (0, -1), "L": (-1, 0), "R": (1, 0)}  def main():    lines = sys.stdin.read().split("\n")    q = int(lines[0])    owner = {}   # (x, y) → 전선 번호. 튜플은 값이 같으면 같은 열쇠다    wires = {}   # 전선 번호 → 그 전선이 차지한 칸들    next_id = 1    out = []    for line in lines[1:1 + q]:        parts = line.split()        x, y = int(parts[1]), int(parts[2])        if parts[0] == "lay":            path = [(x, y)]            for ch in parts[3]:                dx, dy = STEP[ch]                x, y = x + dx, y + dy                path.append((x, y))            hit = next((cell for cell in path if cell in owner), None)  # 길 순서로 처음 막히는 칸            if hit is not None:                out.append(f"blocked {owner[hit]}")  # 아무 칸도 놓지 않는다                continue            mine = list(dict.fromkeys(path))  # 자기 길을 다시 지나는 칸은 한 번만            for cell in mine:                owner[cell] = next_id            wires[next_id] = mine            out.append(f"ok {len(mine)}")            next_id += 1        else:            if (x, y) in owner:                wire = owner[(x, y)]                for cell in wires.pop(wire):                    del owner[cell]  # 값을 0으로 바꾸는 것이 아니라 열쇠를 지운다                out.append(f"removed {wire}")            else:                out.append("none")    out.append(f"{len(wires)} {len(owner)}")    print("\n".join(out))  main()

JavaScriptmain.js · 43 줄

const lines = require("fs").readFileSync(0, "utf8").split("\n"); const STEP = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };const q = Number(lines[0]);const owner = new Map(); // "x,y" → 전선 번호. 배열 [x, y]는 내용이 같아도 다른 열쇠라서 문자열로 만든다const wires = new Map(); // 전선 번호 → 그 전선이 차지한 칸의 열쇠들let nextId = 1;const out = [];for (let t = 1; t <= q; t++) {  const parts = lines[t].trim().split(" ");  let x = Number(parts[1]);  let y = Number(parts[2]);  if (parts[0] === "lay") {    const path = [x + "," + y];    for (const ch of parts[3]) {      x += STEP[ch][0];      y += STEP[ch][1];      path.push(x + "," + y);    }    const hit = path.find((key) => owner.has(key)); // 길 순서로 처음 막히는 칸    if (hit !== undefined) {      out.push("blocked " + owner.get(hit)); // 아무 칸도 놓지 않는다      continue;    }    const mine = [...new Set(path)]; // 자기 길을 다시 지나는 칸은 한 번만    for (const key of mine) owner.set(key, nextId);    wires.set(nextId, mine);    out.push("ok " + mine.length);    nextId++;  } else {    const key = x + "," + y;    if (owner.has(key)) {      const wire = owner.get(key);      for (const k of wires.get(wire)) owner.delete(k); // 값을 바꾸는 것이 아니라 열쇠를 지운다      wires.delete(wire);      out.push("removed " + wire);    } else {      out.push("none");    }  }}out.push(wires.size + " " + owner.size);console.log(out.join("\n"));

TypeScriptmain.ts · 45 줄

import { readFileSync } from "node:fs"; const lines: string[] = readFileSync(0, "utf8").split("\n"); const STEP: Record<string, [number, number]> = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };const q: number = Number(lines[0]);const owner = new Map<string, number>();   // "x,y" → 전선 번호. 배열 [x, y]는 내용이 같아도 다른 열쇠라서 문자열로 만든다const wires = new Map<number, string[]>(); // 전선 번호 → 그 전선이 차지한 칸의 열쇠들let nextId = 1;const out: string[] = [];for (let t = 1; t <= q; t++) {  const parts: string[] = lines[t].trim().split(" ");  let x = Number(parts[1]);  let y = Number(parts[2]);  if (parts[0] === "lay") {    const path: string[] = [x + "," + y];    for (const ch of parts[3]) {      x += STEP[ch][0];      y += STEP[ch][1];      path.push(x + "," + y);    }    const hit: string | undefined = path.find((key: string) => owner.has(key)); // 길 순서로 처음 막히는 칸    if (hit !== undefined) {      out.push("blocked " + owner.get(hit)); // 아무 칸도 놓지 않는다      continue;    }    const mine: string[] = [...new Set(path)]; // 자기 길을 다시 지나는 칸은 한 번만    for (const key of mine) owner.set(key, nextId);    wires.set(nextId, mine);    out.push("ok " + mine.length);    nextId++;  } else {    const key: string = x + "," + y;    const wire: number | undefined = owner.get(key);    if (wire !== undefined) {      for (const k of wires.get(wire) ?? []) owner.delete(k); // 값을 바꾸는 것이 아니라 열쇠를 지운다      wires.delete(wire);      out.push("removed " + wire);    } else {      out.push("none");    }  }}out.push(wires.size + " " + owner.size);console.log(out.join("\n"));

JavaMain.java · 63 줄

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashMap;import java.util.LinkedHashSet;import java.util.List;import java.util.Map;import java.util.Set; public class Main {    // 두 좌표를 long 하나로 묶는다. y가 음수이면 위쪽 32비트가 모두 1이 되므로 아래 32비트만 남기고 합친다.    static long key(int x, int y) {        return ((long) x << 32) | (y & 0xFFFFFFFFL);    }     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        int q = Integer.parseInt(in.readLine().trim());        Map<Long, Integer> owner = new HashMap<>();      // 칸 → 전선 번호        Map<Integer, List<Long>> wires = new HashMap<>(); // 전선 번호 → 그 전선이 차지한 칸들        int nextId = 1;        StringBuilder out = new StringBuilder();        for (int t = 0; t < q; t++) {            String[] parts = in.readLine().trim().split(" ");            int x = Integer.parseInt(parts[1]), y = Integer.parseInt(parts[2]);            if (parts[0].equals("lay")) {                Set<Long> mine = new LinkedHashSet<>(); // 자기 길을 다시 지나는 칸은 한 번만                mine.add(key(x, y));                for (char ch : parts[3].toCharArray()) {                    if (ch == 'U') y++;                    else if (ch == 'D') y--;                    else if (ch == 'L') x--;                    else x++;                    mine.add(key(x, y));                }                Integer hit = null;                for (long k : mine) { // LinkedHashSet은 넣은 순서 = 길 순서                    hit = owner.get(k);                    if (hit != null) break;                }                if (hit != null) {                    out.append("blocked ").append(hit).append('\n'); // 아무 칸도 놓지 않는다                    continue;                }                for (long k : mine) owner.put(k, nextId);                wires.put(nextId, new ArrayList<>(mine));                out.append("ok ").append(mine.size()).append('\n');                nextId++;            } else {                Integer wire = owner.get(key(x, y));                if (wire != null) {                    for (long k : wires.remove(wire)) owner.remove(k); // 열쇠를 지운다                    out.append("removed ").append(wire).append('\n');                } else {                    out.append("none\n");                }            }        }        out.append(wires.size()).append(' ').append(owner.size()).append('\n');        System.out.print(out);    }}

C#Main.cs · 66 줄

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int q = int.Parse(Console.ReadLine().Trim());        var owner = new Dictionary<(int, int), int>();       // 칸 → 전선 번호. 값 튜플은 값이 같으면 같은 열쇠다        var wires = new Dictionary<int, List<(int, int)>>(); // 전선 번호 → 그 전선이 차지한 칸들        int nextId = 1;        var sb = new StringBuilder();        for (int t = 0; t < q; t++)        {            string[] parts = Console.ReadLine().Trim().Split(' ');            int x = int.Parse(parts[1]), y = int.Parse(parts[2]);            if (parts[0] == "lay")            {                var path = new List<(int, int)> { (x, y) };                foreach (char ch in parts[3])                {                    if (ch == 'U') y++;                    else if (ch == 'D') y--;                    else if (ch == 'L') x--;                    else x++;                    path.Add((x, y));                }                int hit = 0;                foreach (var cell in path)                {                    if (owner.TryGetValue(cell, out hit)) break; // 길 순서로 처음 막히는 칸                    hit = 0;                }                if (hit != 0)                {                    sb.Append("blocked ").Append(hit).Append('\n'); // 아무 칸도 놓지 않는다                    continue;                }                var mine = new List<(int, int)>();                foreach (var cell in path)                {                    if (owner.TryAdd(cell, nextId)) mine.Add(cell); // 자기 길을 다시 지나는 칸은 한 번만                }                wires[nextId] = mine;                sb.Append("ok ").Append(mine.Count).Append('\n');                nextId++;            }            else            {                if (owner.TryGetValue((x, y), out int wire))                {                    foreach (var cell in wires[wire]) owner.Remove(cell); // 열쇠를 지운다                    wires.Remove(wire);                    sb.Append("removed ").Append(wire).Append('\n');                }                else                {                    sb.Append("none\n");                }            }        }        sb.Append(wires.Count).Append(' ').Append(owner.Count).Append('\n');        Console.Write(sb);    }}

C++main.cpp · 59 줄

#include <iostream>#include <map>#include <string>#include <utility>#include <vector>using namespace std; int main() {    int q;    cin >> q;    map<pair<int, int>, int> owner;            // 칸 → 전선 번호. pair는 값으로 비교된다    map<int, vector<pair<int, int>>> wires;    // 전선 번호 → 그 전선이 차지한 칸들    int nextId = 1;    for (int t = 0; t < q; t++) {        string cmd;        int x, y;        cin >> cmd >> x >> y;        if (cmd == "lay") {            string steps;            cin >> steps;            vector<pair<int, int>> path = {{x, y}};            for (char ch : steps) {                if (ch == 'U') y++;                else if (ch == 'D') y--;                else if (ch == 'L') x--;                else x++;                path.push_back({x, y});            }            int hit = 0;            for (const auto& cell : path) {                auto it = owner.find(cell); // owner[cell]로 물으면 없는 칸이 0으로 생겨 버린다                if (it != owner.end()) { hit = it->second; break; }            }            if (hit != 0) {                cout << "blocked " << hit << "\n"; // 아무 칸도 놓지 않는다                continue;            }            vector<pair<int, int>> mine;            for (const auto& cell : path) {                if (owner.insert({cell, nextId}).second) mine.push_back(cell); // 자기 길을 다시 지나는 칸은 한 번만            }            cout << "ok " << mine.size() << "\n";            wires[nextId] = mine;            nextId++;        } else {            auto it = owner.find({x, y});            if (it != owner.end()) {                int wire = it->second;                for (const auto& cell : wires[wire]) owner.erase(cell); // 열쇠를 지운다                wires.erase(wire);                cout << "removed " << wire << "\n";            } else {                cout << "none\n";            }        }    }    cout << wires.size() << " " << owner.size() << "\n";    return 0;}

Cmain.c · 99 줄

#include <stdio.h>#include <string.h> /* C에는 사전이 없어서 해시 표를 직접 만든다.   칸은 (x, y, 전선 번호)이고, 빈 칸은 state 0, 쓰는 칸은 1, 지운 자리는 2(찾을 때 건너뛰고 계속 본다). */#define SLOTS (1 << 19) /* 놓는 칸은 모두 합쳐 2,000 × 101 = 202,000개 이하라 표가 차지 않는다 */#define MAXQ 2000#define MAXLEN 100 static int slot_x[SLOTS], slot_y[SLOTS], slot_id[SLOTS];static char state[SLOTS];static int wire_x[MAXQ + 1][MAXLEN + 1], wire_y[MAXQ + 1][MAXLEN + 1], wire_cells[MAXQ + 1]; static unsigned hash(int x, int y) {    unsigned h = (unsigned)x * 2654435761u ^ ((unsigned)y * 40503u + 0x9e3779b9u);    h ^= h >> 15;    return h & (SLOTS - 1);} /* (x, y)가 든 자리를 돌려준다. 없으면 -1 */static int find(int x, int y) {    unsigned h = hash(x, y);    while (state[h] != 0) {        if (state[h] == 1 && slot_x[h] == x && slot_y[h] == y) return (int)h;        h = (h + 1) & (SLOTS - 1);    }    return -1;} static void insert(int x, int y, int id) {    unsigned h = hash(x, y);    while (state[h] == 1) h = (h + 1) & (SLOTS - 1);    state[h] = 1;    slot_x[h] = x;    slot_y[h] = y;    slot_id[h] = id;} int main(void) {    int q;    if (scanf("%d", &q) != 1) return 0;    int next_id = 1, wire_count = 0, cell_count = 0;    for (int t = 0; t < q; t++) {        char cmd[8];        int x, y;        if (scanf("%7s %d %d", cmd, &x, &y) != 3) return 0;        if (strcmp(cmd, "lay") == 0) {            char steps[MAXLEN + 2];            if (scanf("%101s", steps) != 1) return 0;            int len = (int)strlen(steps);            int px[MAXLEN + 1], py[MAXLEN + 1];            px[0] = x;            py[0] = y;            for (int i = 0; i < len; i++) {                if (steps[i] == 'U') y++;                else if (steps[i] == 'D') y--;                else if (steps[i] == 'L') x--;                else x++;                px[i + 1] = x;                py[i + 1] = y;            }            int hit = 0;            for (int i = 0; i <= len && hit == 0; i++) {                int at = find(px[i], py[i]); /* 길 순서로 처음 막히는 칸 */                if (at >= 0) hit = slot_id[at];            }            if (hit != 0) {                printf("blocked %d\n", hit); /* 아무 칸도 놓지 않는다 */                continue;            }            int n = 0;            for (int i = 0; i <= len; i++) {                if (find(px[i], py[i]) >= 0) continue; /* 자기 길을 다시 지나는 칸은 한 번만 */                insert(px[i], py[i], next_id);                wire_x[next_id][n] = px[i];                wire_y[next_id][n] = py[i];                n++;            }            wire_cells[next_id] = n;            wire_count++;            cell_count += n;            printf("ok %d\n", n);            next_id++;        } else {            int at = find(x, y);            if (at >= 0) {                int wire = slot_id[at];                for (int i = 0; i < wire_cells[wire]; i++) state[find(wire_x[wire][i], wire_y[wire][i])] = 2;                wire_count--;                cell_count -= wire_cells[wire];                printf("removed %d\n", wire);            } else {                printf("none\n");            }        }    }    printf("%d %d\n", wire_count, cell_count);    return 0;}

Craykonmain.cray · 83 줄

q = 콘솔.줄읽기().수로변환();owner = 사전(); // "x,y" → 전선 번호. 열쇠는 두 좌표를 쉼표로 이은 문자열wires = 사전(); // 전선 번호 → 그 전선이 차지한 칸의 열쇠들nextId = 1;반복 (t = 0; t < q; t++){    parts = 콘솔.줄읽기().공백제거().나누기(" ");    x = parts[1].수로변환();    y = parts[2].수로변환();    만약 (parts[0] == "lay")    {        path = ["" + x + "," + y];        steps = parts[3];        반복 (i = 0; i < steps.길이; i++)        {            ch = steps.부분문자열(i, 1);            만약 (ch == "U")            {                y = y + 1;            }            아니면 만약 (ch == "D")            {                y = y - 1;            }            아니면 만약 (ch == "L")            {                x = x - 1;            }            아니면            {                x = x + 1;            }            path.넣기("" + x + "," + y);        }        hit = 0;        각각 (key 에서 path)        {            만약 (owner.있나(key))            {                hit = owner[key]; // 길 순서로 처음 막히는 칸                그만;            }        }        만약 (hit != 0)        {            콘솔.쓰기("blocked " + hit); // 아무 칸도 놓지 않는다        }        아니면        {            mine = [];            각각 (key 에서 path)            {                만약 (!owner.있나(key))                {                    owner[key] = nextId;                    mine.넣기(key);                }            }            wires[nextId] = mine;            콘솔.쓰기("ok " + mine.개수);            nextId = nextId + 1;        }    }    아니면    {        key = "" + x + "," + y;        만약 (owner.있나(key))        {            wire = owner[key];            각각 (k 에서 wires[wire])            {                owner.빼기(k); // 값을 바꾸는 것이 아니라 열쇠를 지운다            }            wires.빼기(wire);            콘솔.쓰기("removed " + wire);        }        아니면        {            콘솔.쓰기("none");        }    }}콘솔.쓰기(wires.개수 + " " + owner.개수);