[파이썬] 백준 18428 : 감시피하기 (골드5)

[파이썬] 백준 18428 : 감시피하기 (골드5)

18428번: 감시 피하기

---

문제

---

풀이

 

0. 방향성 생각

• 조합으로 벽 설치 경우의 수 구하기
• 선생님 수가 적으므로 선생님 기준으로 학생 찾기

1. 입력

from itertools import combinations as C
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = [list(input().split()) for _ in range(n)]
empty,student,teacher = set(),set(),set()
for i in range(n):
    for j in range(n):
        if arr[i][j] == 'X': empty.add((j,i))
        elif arr[i][j] == 'S': student.add((j,i))
        elif arr[i][j] == 'T': teacher.add((j,i))

comb = list(C(empty,3))

•  

2. 함수 정의

def check(wall):
    for x,y in teacher:
        
        for j in range(x+1,n):
            if (j,y) in student:
                return 'NO'
            if (j,y) in wall:
                break
            
        for j in range(x-1,-1,-1):
            if (j,y) in student:
                return 'NO'
            if (j,y) in wall:
                break
            
        for i in range(y+1,n):
            if (x,i) in student:
                return 'NO'
            if (x,i) in wall:
                break
            
        for i in range(y-1,-1,-1):
            if (x,i) in student:
                return 'NO'
            if (x,i) in wall:
                break
    return 'YES'

• WALL 위치 3개가 들어온다.
• 선생님 좌표를 기준으로 탐색시작.
• 상 하 좌 우 탐색
• 탐색 중 벽을 만나면 그 방향은 그만탐색
• 탐색 중 학생 만나면 바로 NO 리턴

3. 출력

for c in comb:
    if check(c) == 'YES':
        print('YES')
        break
else:
    print('NO')

• 하나라도 YES면 YES, 아니면 No

 

---

전체코드

from itertools import combinations as C
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = [list(input().split()) for _ in range(n)]
empty,student,teacher = set(),set(),set()
for i in range(n):
    for j in range(n):
        if arr[i][j] == 'X': empty.add((j,i))
        elif arr[i][j] == 'S': student.add((j,i))
        elif arr[i][j] == 'T': teacher.add((j,i))

comb = list(C(empty,3))

def check(wall):
    for x,y in teacher:
        
        for j in range(x+1,n):
            if (j,y) in student:
                return 'NO'
            if (j,y) in wall:
                break
            
        for j in range(x-1,-1,-1):
            if (j,y) in student:
                return 'NO'
            if (j,y) in wall:
                break
            
        for i in range(y+1,n):
            if (x,i) in student:
                return 'NO'
            if (x,i) in wall:
                break
            
        for i in range(y-1,-1,-1):
            if (x,i) in student:
                return 'NO'
            if (x,i) in wall:
                break
    return 'YES'

for c in comb:
    if check(c) == 'YES':
        print('YES')
        break
else:
    print('NO')

 

코멘트

감시랑 비슷해서 똑같이 푼듯. 더 쉬운버전