[BOJ][Python] 백준 16226 번: 거울냥이는 죽어서 거울을 남긴다

1일 1PS 69일차!

📚 문제

---

골드 2 거울냥이는 죽어서 거울을 남긴다

💡 풀이 과정

---

• 냥이들을 모두 기록하고 dfs 처럼 다루기에는 그 수가 너무 많다.
• 빔은 아래로는 발사되지 않기에 열 단위로 나누는 것이 맞다고 판단해서 열을 key 값으로 한 dic 을 생성했다.
• 열 단위로 정렬 후 거울로 구분된 냥이의 수를 세면 된다.

📌포인트

---

• 이냥이들의 순서를 기록하지 않아도 되는 이유
  • 거울은 항상 냥이 아래에 설치되기에 빔은 왼쪽 위 오른쪽으로 밖에 못날라간다.
  • 이때 다른 냥이들도 모두 아래에 빔이 설치되어있기에 아래에서 올라오는 빔에 맞아 죽지는 않는다.
  • 즉 냥이들은 오른쪽, 왼쪽의 빔으로만 죽을 수 있다.
  • 이때 빔은 냥이들을 모두 통과하기 때문에 살아있는 냥이의 숫자에는 순서가 영향을 끼치지 않는다.
    • OOOO 네 마리의 냥이가 존재할 때 어느 냥이가 먼저 빔을 쏘더라도 한 마리의 냥이만 남게된다.
      • OXXX, XOXX, XXOX, XXXO
  • 결국 “거울 냥이 거울 냥이” 이렇게 거울로 구분되어진 냥이가 몇마리인지가 각 행에서 살아남은 냥이의 수이다.
• 가장 처음에는 왼쪽에 거울이 없더라도 살아남을 수 있기에 초기 flag 를 true 로 설정한다.

💻 코드

---

input = sys.stdin.readline

N = int(input())
# 빔은 가로와 위로 나가기 때문에 열을 기준으로 거울, 냥이 기록
board = {}
# 살아있는 냥이의 수
cnt = 0

for _ in range(N):
    x, y = map(int, input().split())
    if x not in board:
        board[x] = []
    if x + 1 not in board:
        board[x + 1] = []

    # 냥이(0)의 위치 설정,
    board[x].append([y, 0])
    # 거울(1)의 위치 설정
    board[x + 1].append([y, 1])

for x in board:
    # 열들을 오름차순 정렬
    board[x].sort(key= lambda x: x[0])

    # flag = True 일 때 나오는 냥이는 살아남는 냥이다.
    flag = True
    for y, isCat in board[x]:

        # 거울을 만난 경우 flag 를 True 로 둔다.
        if isCat == 1:
            flag = True

        else:
            # flag 가 true 라면 다음 냥이들 중 한마리는 살아남는다.
            if flag:
                cnt += 1
                flag = False
            # flag 가 false 라면 이미 거울 다음 냥이를 카운팅 했다.

print(cnt)