백준 5884 감시 카메라 / python

문제 : 5884

풀이 point

입력 받은 카메라를 고정한 후 모든 행, 열에 대하여 검증하는 방법을 쓰면 된다.

풀이 방법

먼저, X와Y에 대한 좌표별 등장 횟수를 센다.

만약 등장한 x, y의 개수가 3이하면 가능하니 1을 출력하고 종료한다.

그외에는 인접리스트를 생성해서 검증한다.
x인덱스에 해당하는 점들이 가진 y인덱스 리스트와
y인덱스에 해당하는 점들이 가진 x인덱스 리스트를 만든다.

첫번째 경우의 수 - 하나의 세로선 + 최대 두 가로선
현재 세로선 위에 있으면서 유일하게 등장하는 y좌표 개수(세로 선으로 덮기 가능)
-> 굳이 하나인 이유는 하나가 아니면 한 선으로는 커버가 불가능 하기 때문

그걸 제외하고 남은 점들이 차지하는 고유 y좌표 수(모든 y좌표 개수, 중복 제외)
idy - cnt가 2이하면 가능(모든 y좌표 개수 - 내가 세로선 하나로 커버 가능한 y좌표)

두번째 경우의 수 - 하나의 가로선 + 최대 두 세로선
위와 마찬가지로 수행

코드

N = int(input())

points = [tuple(map(int, input().split())) for _ in range(N)]

xIdx = {}; yIdx = {}
xcount = []; ycount = []

idx = 0
for x, _ in points:
    if x not in xIdx:
        xIdx[x] = idx
        xcount.append(0)
        idx += 1
    xcount[xIdx[x]] += 1

idy = 0

for _, y in points:
    if y not in yIdx:
        yIdx[y] = idy
        ycount.append(0)
        idy += 1
    ycount[yIdx[y]] += 1

if idx <= 3 or idy <= 3:
    print(1)
    exit()
    
xList = [[] for _ in range(idx)]
yList = [[] for _ in range(idy)]

for x, y in points:
    xi = xIdx[x]
    yi = yIdx[y]
    xList[xi].append(yi)
    yList[yi].append(xi)

for xi in range(idx):
    cnt = sum(1 for yi in xList[xi] if ycount[yi] == 1)
    if idy - cnt <= 2:
        print(1)
        exit()

for yi in range(idy):
    cnt = sum(1 for xi in yList[yi] if xcount[xi] == 1)
    if idx - cnt <= 2:
        print(1)
        exit()

print(0)