문제 링크
문제 요약
주어진 n x m 크기의 흑백 격자 그림(.은 흰색, #은 검은색)을 보고, 노노그램 문제의 힌트에 해당하는 숫자들을 출력하는 문제입니다.
각 행과 열에 대해 연속된 검은색 칸(#) 덩어리(세그먼트)의 길이들을 순서대로 찾아야 합니다.
풀이
이 문제는 주어진 그림에서 노노그램의 힌트를 역으로 찾아내는 구현 문제입니다. 일본식 크로스워드의 힌트는 각 행과 열에 존재하는 검은색 블록들의 길이를 순서대로 나타냅니다.
접근 방식:
-
입력 처리: 먼저
n과m을 입력받고, 이어서n개의 문자열로 이루어진 격자판을 입력받아 저장합니다. -
행(Row) 힌트 계산:
- 각 행에 대해 반복합니다.
- 현재 행을 왼쪽에서 오른쪽으로 순회하면서 연속된 검은색 칸(
'#')의 개수를 세는cnt변수를 유지합니다. '#'를 만나면cnt를 1 증가시킵니다.'.'를 만나거나 행의 끝에 도달했을 때, 만약cnt가 0보다 크다면, 이는 이전에 연속된 검은색 블록이 끝났음을 의미하므로,cnt값을 현재 행의 힌트 목록에 추가하고cnt를 0으로 초기화합니다.- 행의 순회가 끝났을 때,
cnt가 0보다 크다면 마지막 블록이 행의 끝에서 끝난 경우이므로,cnt값을 힌트 목록에 추가합니다. - 이렇게 계산된 각 행의 힌트 목록들을 저장합니다.
-
열(Column) 힌트 계산:
- 각 열에 대해 반복합니다.
- 현재 열을 위에서 아래로 순회하면서 위와 동일한 방식으로
cnt를 사용하여 연속된 검은색 칸의 길이를 계산하고 힌트 목록에 추가합니다. - 이렇게 계산된 각 열의 힌트 목록들을 저장합니다.
-
출력:
- 먼저 계산된 행 힌트들을 문제에서 요구하는 형식(세그먼트 개수, 이어서 세그먼트 길이들)으로 출력합니다.
- 이어서 빈 줄을 출력합니다.
- 마지막으로 계산된 열 힌트들을 동일한 형식으로 출력합니다.
이 과정은 격자판을 두 번(한 번은 행, 한 번은 열) 순회하며 간단한 카운팅을 수행하는 것으로 구현될 수 있습니다.
정답 코드
"""
[28652: Японский кроссворд](https://www.acmicpc.net/problem/28652)
Tier: Bronze 1
Category: implementation, string
"""
import sys
from math import sqrt, pi, sin, factorial, ceil, floor
from datetime import datetime, timedelta
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, product
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
from operator import itemgetter, attrgetter, mul, add, sub, truediv
from typing import List, Tuple, Dict, Set, Any, Union
SYS_INPUT = True
RECURSION_LIMIT = 10 ** 7
SET_RECURSION = False
BLANK = " "
if SET_RECURSION:
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda : sys.stdin.readline().rstrip() if SYS_INPUT else input()
mii = lambda : [*map(int,inp().split())]
mfi = lambda : [*map(float,inp().split())]
ii = lambda : int(inp())
fi = lambda : float(inp())
isplit = lambda : inp().split()
p = print
def gcd(a, b): return gcd(b, a % b) if b > 0 else a
def lcm(a, b): return a * b // gcd(a, b)
def solve():
n, m = mii()
grid = [inp() for _ in range(n)]
rows = []
cols = []
# 행 힌트 계산
for i in range(n):
current = [] # 현재 행의 힌트 리스트
cnt = 0 # 연속된 '#' 개수 카운터
for j in range(m):
if grid[i][j] == '#':
cnt += 1
else: # '.'를 만난 경우
if cnt > 0: # 이전에 연속된 '#'가 있었다면
current.append(cnt) # 힌트 리스트에 추가
cnt = 0 # 카운터 초기화
# 행의 끝에 도달했을 때, 마지막 블록이 '#'으로 끝나는 경우 처리
if cnt > 0:
current.append(cnt)
rows.append(current) # 계산된 행 힌트를 전체 행 힌트 리스트에 추가
# 열 힌트 계산
for j in range(m): # 열을 기준으로 순회
current = [] # 현재 열의 힌트 리스트
cnt = 0
for i in range(n): # 행을 순회하며 열의 요소에 접근
if grid[i][j] == '#':
cnt += 1
else: # '.'를 만난 경우
if cnt > 0:
current.append(cnt)
cnt = 0
# 열의 끝에 도달했을 때, 마지막 블록이 '#'으로 끝나는 경우 처리
if cnt > 0:
current.append(cnt)
cols.append(current) # 계산된 열 힌트를 전체 열 힌트 리스트에 추가
# 행 힌트 출력
for i in range(n):
print(len(rows[i]), *rows[i]) # 힌트 개수와 힌트 내용 출력
print() # 행 힌트와 열 힌트 사이에 빈 줄 출력
# 열 힌트 출력
for j in range(m):
print(len(cols[j]), *cols[j])
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()