[Alogorithm] D-18 감시 피하기 18428.py 인구이동 16234.py

감시 피하기

from itertools import combinations

n = int(input()) # 복도의 크기
board = [] # 복도 정보 (N x N)
teachers = [] # 모든 선생님 위치 정보
spaces = [] # 모든 빈 공간 위치 정보

for i in range(n):
    board.append(list(input().split()))
    for j in range(n):
        # 선생님이 존재하는 위치 저장
        if board[i][j] == 'T':
            teachers.append((i, j))
        # 장애물을 설치할 수 있는 (빈 공간) 위치 저장
        if board[i][j] == 'X':
            spaces.append((i, j))

# 특정 방향으로 감시를 진행 (학생 발견: True, 학생 미발견: False)
def watch(x, y, direction):
    # 왼쪽 방향으로 감시
    if direction == 0:
        while y >= 0:
            if board[x][y] == 'S': # 학생이 있는 경우
                return True
            if board[x][y] == 'O': # 장애물이 있는 경우
                return False
            y -= 1
    # 오른쪽 방향으로 감시
    if direction == 1:
        while y < n:
            if board[x][y] == 'S': # 학생이 있는 경우
                return True
            if board[x][y] == 'O': # 장애물이 있는 경우
                return False
            y += 1
    # 위쪽 방향으로 감시
    if direction == 2:
        while x >= 0:
            if board[x][y] == 'S': # 학생이 있는 경우
                return True
            if board[x][y] == 'O': # 장애물이 있는 경우
                return False
            x -= 1
    # 아래쪽 방향으로 감시
    if direction == 3:
        while x < n:
            if board[x][y] == 'S': # 학생이 있는 경우
                return True
            if board[x][y] == 'O': # 장애물이 있는 경우
                return False
            x += 1
    return False

# 장애물 설치 이후에, 한 명이라도 학생이 감지되는지 검사
def process():
    # 모든 선생의 위치를 하나씩 확인
    for x, y in teachers:
        # 4가지 방향으로 학생을 감지할 수 있는지 확인
        for i in range(4):
            if watch(x, y, i):
                return True
    return False

find = False # 학생이 한 명도 감지되지 않도록 설치할 수 있는지의 여부

# 빈 공간에서 3개를 뽑는 모든 조합을 확인
for data in combinations(spaces, 3):
    # 장애물들을 설치해보기
    for x, y in data:
        board[x][y] = 'O'
    # 학생이 한 명도 감지되지 않는 경우
    if not process():
        # 원하는 경우를 발견한 것임
        find = True
        break
    # 설치된 장애물을 다시 없애기
    for x, y in data:
        board[x][y] = 'X'

if find:
    print('YES')
else:
    print('NO')

분석 좀 해봐야겠다

감시 피하기

from collections import deque

# NLR
n, l, r = map(int, input().split())
# 지도
data = []
# 방문기록
visited = [[0] * n for _ in range(n)]
# 연합
union = []
#상하좌우
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(n):
    data.append(list(map(int, input().split())))

result = 0
queue = deque()


while True:
    # 연합국 있는지 없는지(True 빠져나오기 위한)
    ischecked = False
    for i in range(n):
        for j in range(n):
            # 반문 안했으면
            if visited[i][j] == 0:
                visited[i][j] = 1
                sum = data[i][j]
                queue.append([i, j])
                union = [[i, j]]

                while queue:
                    x, y = queue.popleft()
                    #상하좌우 검사
                    for o in range(4):
                        ix = x + dx[o]
                        iy = y + dy[o]
                        #맵 빠져나가면
                        if ix < 0 or ix >= n or iy < 0 or iy >= n:
                            continue
                        # l 보다 크고 r보다 적으면서 방문안한 지역
                        if l <= abs(data[x][y] - data[ix][iy]) <= r and visited[ix][iy] == 0:
                            ischecked = True
                            #방문기록
                            visited[ix][iy] = 1
                            # sum 더함
                            sum += data[ix][iy]
                            # 연합국 더함
                            union.append([ix, iy])
                            # 큐에 더함
                            queue.append([ix, iy])
                # 한개 따라 연합국 모두 더하면 연합국에 따라 다 더한값/연합국 개수 인구수 바꿔줌
                for g, h in union:
                    data[g][h] = sum // len(union)
    # 연합국 존재하면
    if ischecked:
        result += 1
    # 연합국 없으면 종료
    else:
        break
    # 다시 초기화 하는 이유? 방문 기록을 없애야 새롭게 연합국 맺을 수 잇음
    visited = [[0] * n for _ in range(n)]

print(result)

3번 문제는 취업을 준비할 시기 미래의 나에게 맡긴다...