https://www.acmicpc.net/problem/18156
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 14311 | 3948 | 3186 | % |
문제
n x n 격자가 주어지며, 각 칸은 흑색 또는 백색으로 칠해져 있습니다. 다음 조건을 모두 만족하면 격자는 ‘올바른’ 것으로 간주됩니다:
- 모든 행에서 흑색 칸의 수와 백색 칸의 수가 같아야 합니다.
- 모든 열에서 흑색 칸의 수와 백색 칸의 수가 같아야 합니다.
- 어떤 행이나 열에서도 같은 색상의 칸이 3개 이상 연속으로 있어서는 안 됩니다.
주어진 격자가 올바른지 판단하세요.
입력
첫 줄에는 정수 n이 주어집니다 (2 ≤ n ≤ 24; n은 짝수).
그 다음 n개의 줄에는 각각 길이 n의 문자열이 주어지며, 'B’와 'W’로만 구성되어 있습니다. 이는 격자 칸의 색상을 나타냅니다.
출력
격자가 올바르다면 단일 줄에 숫자 1을 출력하세요. 그렇지 않다면 단일 줄에 숫자 0을 출력하세요.
예제 입력 1
4
WBBW
WBWB
BWWB
BWBW
예제 출력 1
1
예제 입력 2
4
BWWB
BWBB
WBBW
WBWW
예제 출력 2
0
예제 입력 3
6
BWBWWB
WBWBWB
WBBWBW
BBWBWW
BWWBBW
WWBWBB
예제 출력 3
0
예제 입력 4
6
WWBBWB
BBWWBW
WBWBWB
BWBWBW
BWBBWW
WBWWBB
예제 출력 4
1
문제는 모든 행과 열에 W와 B의 개수가 같은지
모든 행과 열에 3개 이상 연속되는 같은 문자가 없는지 확인하면 쉽게 풀 수 있다.
하지만 바이트 문자와 합계를 이용하면 횡방향과 종방향의 조건 검사를 더 빨리 풀 수 있겠다는 생각이 들었다.
특히 보드가 정 사각형이기 때문에 더 쉬웠다.
코드 설명
입력 처리
import os
n, *r = os.read(0, os.fstat(0).st_size).split()
n = int(n)
r = [[1&e for e in row] for row in r]os.read() 함수를 통해 입력을 읽을 때 디코딩 하지 않으면 바이트 문자로 읽게 된다.
표준입력인 0 에서 os.fstat(0).st_size로 버퍼 길이를 측정하고 버퍼 길이만큼 읽어온다.
보통은 따로 귀찮게 디코딩을 해 주어야 하는 것이 단점이 되는데 여기서는 W와 B를 숫자로 읽어 올 수 있다는 장점이 된다.
바이트 문자는 각 문자를 아스키 코드의 숫자로 읽어오는데, W는 87 B는 66이 된다.
87과 66을 가공하지 않고 조건 계산식을 만드는 방법도 있었지만 좀 더 식을 만들기 쉽게 하기 위해서1&e를 해 주었다.
이 비트연산은 이진수 마지막 비트가 1이면 1 0이면 0을 반환하므로 홀수인 W는 1 짝수인 B는 0으로 변환되어 2차원 배열로 저장된다.
이해를 돕기 위해 처리 과정을 출력해서 살펴보면 아래와 같다.
sys를 이용해서 바이트 상태로 버퍼를 바로 읽고 싶으면 이렇게 해도 된다.
import sys
n,*r=sys.stdin.buffer.read().split()행과 열의 합 검사
chksum = set([sum(row) for row in r] + [sum(col) for col in zip(*r)])
if chksum != {n >> 1}:
print(0)
exit()
sum(row)를 통해 각 행의 합을 계산하고, zip(*r)를 사용하여 각 열의 합도 계산한다.
행과 열의 합이 동일한지를 확인하기 위해 set 자료형을 사용하여 중복된 값을 제거하고, 그 결과가 {n >> 1}와 같은지 비교한다.
여기서 n >> 1은 n을 오른쪽으로 1비트 시프트(즉, 2로 나누기)한 값. 만약 행과 열의 합이 모두 이 값과 같지 않다면 0을 출력하고 프로그램을 종료한다.
간단한 예외 처리
if n == 2:
print(1)
exit()
n이 2일 때는 바로 1을 출력하고 프로그램을 종료. 지금까지의 조건을 통과했다면 2사이즈에서는 더 이상의 검사가 필요 없기 때문이다.
3연속 0 또는 3이 나오는지 검사
for i in range(n):
for j in range(n - 2):
if {0, 3} & {r[i][j] + r[i][j + 1] + r[i][j + 2], r[j][i] + r[j + 1][i] + r[j + 2][i]}:
print(0)
exit()
이 부분에서는 격자 내에서 동일한 숫자가 세 번 연속 나오는지를 검사한다.
가로 및 세로 방향을 동시에 검사하는데 r[i][j] + r[i][j + 1] + r[i][j + 2]와 같은 표현을 통해 특정 구간의 합을 계산하며, 만약 합이 0 또는 3이라면 해당 구간에 모두 0 혹은 1이 연속으로 배치된 것을 의미한다.
교집합을 이용해 하나라도 그런 조건에 해당되는 것이 있는지 찾으며 이 경우 조건에 위배되므로 0을 출력하고 프로그램을 종료한다.
모든 조건을 만족하는 경우
print(1)
모든 조건을 통과하면 1을 출력한다.
최종 코드는 다음과 같다.
def s():
import os
n,*r=os.read(0, os.fstat(0).st_size).split()
n=int(n)
r = [[1 & e for e in row] for row in r]
chksum = set([sum(row) for row in r] + [sum(col) for col in zip(*r)])
if chksum!={n>>1}:
print(0)
exit()
if n==2:
print(1)
exit()
for i in range(n):
for j in range(n - 2):
if {0, 3} & {r[i][j]+r[i][j+1]+r[i][j+2], r[j][i]+r[j+1][i]+r[j+2][i]}:
print(0)
exit()
print(1)
s()
추가로 이 문제들도 바이트 상태로 처리해서 풀 수 있다.