👨‍💻
Hamin TIL
  • Today I Learned 🧑🏻‍💻
  • 회고
  • git
    • git_basics
      • Git 101
      • Git branch
      • Git_ignore
    • Git Book
    • 우아한형제들
    • pull_request
  • db
    • DA
      • 데이터표준화
      • 데이터_요건분석
      • 전사아키텍처_이해
      • 데이터모델링
    • SQL
      • SQL기본및활용
        • SQL활용
          • 절차형SQL
          • 계층형질의와셀프조인
          • DCL
          • 그룹함수
          • 윈도우함수
          • 표준조인
          • 집합연산자
          • 서브쿼리
        • SQL고급활용및튜닝
          • 옵티마이저와실행계획
          • 조인수행원리
          • 인덱스기본
        • SQL기본
          • 함수
          • 관계형데이터베이스개요
          • GROUPBY,HAVING절
          • DDL
          • 조인
          • ORDERBY절
          • DML
          • WHERE절
          • TCL
      • 데이터모델링의이해
        • 데이터모델과성능
          • 정규화의 성능
          • 데이터베이스구조와성능
          • 분산데이터베이스와성능
          • 대량 데이터에 따른 성능
          • 반정규화와 성능
          • 성능데이터모델링의 개요
        • 데이터모델링의이해
          • 식별자
          • 속성
          • 관계
          • 엔터티
          • 데이터 모델의 이해
    • DB
  • trouble
    • libomp
    • After macOS update, git command
    • system
  • algorithm
    • BOJ
      • 평범한 배낭
      • 17825-주사위윷놀이
      • 14888-연산자끼워넣기
      • 14503-로봇청소기
      • 10157
      • 14502-연구소
      • 18428-감시피하기
      • 14501
      • 18405-경쟁적전염
      • 14499-주사위굴리기
      • 16236-아기상어
      • 15686-치킨배달
      • 19237-어른상어
      • 16234-인구이동
      • 19236-청소년상어
      • 1339-단어수학
      • 리모콘
      • 18353 - 병사배치하기
      • 18352-특정거리의도시찾기
      • 12100-2048
      • N-Queen
      • 3190-뱀
      • 11724
    • programmers
      • 영어끝말잇기
      • 기둥과 보
      • H - index
      • 정수삼각형
      • 2018 KAKAO BLIND RECRUITMENT - 압축
      • 삼각달팽이
      • 거스름돈
      • [1차] 셔틀버스
    • data_structure
      • Queue
      • Graph
      • Stack
      • Hash table
    • implementation
      • dynamic_programming
      • sort
      • Least common multiple
      • dfs
      • dijkstra
      • bfs
      • binary_search
    • aps
      • notes
    • modules
  • python
    • requirements.txt
    • Jupyter notebook
    • 00_들어가기 전에
    • Python Virtual Environment
    • Python Syntax
  • django
    • Class Based View in Django
    • Model in Django
    • URL Name
    • Form and ModelForm
    • Authentication
    • Tips & Tricks
    • Optimization
    • Request and Response Objects
    • Templates
    • Variable Routing & DTL
    • Django REST API with JSON web token (JWT)
    • Intro to Django
    • Django REST Framework
    • Wrap-up
    • Image Upload
  • javascript
    • Ajax (Asynchronous Javascript And XML)
    • Document Object Model
    • Java Script 101
    • ES (ECMAscript)
  • java
    • Java 101
  • aws
    • beginning_cloud_computing_with_aws
      • 02 AWS 주요 서비스 이해하기
      • 01 아마존 웹 서비스 Cloud 개요
  • programming
    • Communication
    • CS_용어사전
  • vue.js
    • 01_Vue.js_Intro
  • data_science
    • 01_데이터에서인사이트발견하기
    • pandas
    • 04_데이터분류모델
    • 02_텍스트마이닝첫걸음
    • 05_종합예제
    • 03_미래를예측하는데이터분석
    • Statistics
      • 모수와 추정량
    • 통계학노트
  • linux
    • Linux Commands
  • ide
    • VScode
    • Pycharm
  • html,css
    • HTML 101
    • CSS 101
  • colab
    • colab_101
  • 의사결정나무및모형비교
Powered by GitBook
On this page

Was this helpful?

  1. algorithm
  2. BOJ

18428-감시피하기

Previous14502-연구소Next14501

Last updated 4 years ago

Was this helpful?

  1. 장애물 3 개를 설치하는 모든 경우의 수 순열

  2. 각 경우마다 학생이 들키지 않는지 검사

  3. 중간에 한 명도 안 들킨 경우가 생겼다면 YES 출력하고 exit()

# 학생을 발견하면 발견표시 남기자
def see(y,x,dir):
    global n, triger

    ny = y + dy[dir]
    nx = x + dx[dir]

    if 0 <= ny < n and 0 <= nx < n:
        if temp[ny][nx] == 'S':
            triger = 'ON'
            return
        elif temp[ny][nx] == 'O':
            return
        elif temp[ny][nx] == "X":
            see(ny,nx,dir)
    else:
        return

from itertools import combinations

n = int(input())
arr = [list(input().split()) for _ in range(n)]

dy = [-1,1,0,0]
dx = [0,0,1,-1]

# 선생님들의 위치
t_locs = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == 'T':
            t_locs.append((i,j))

# 장애물을 설치할 수 있는 경우의 수
x_locs = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == 'X':
            x_locs.append((i,j))
o_cases = list(combinations(x_locs,3))

# 장애물 위치 정보 경우들로 반복문
# 장애물을 설치한 한 경우에서..! 모든 선생님의 상하좌우에서 True 라면 끝
poss = "NO"
for o_case in o_cases:
    temp = [arr[i][:] for i in range(len(arr))]

    # 장애물 설치
    for i in range(3):
        temp[o_case[i][0]][o_case[i][1]] = 'O'

    # 장애물 설치된 복도에서 모든 선생님들 감시를 해보자
    triger = 'OFF'
    for ty,tx in t_locs:
        for i in range(4):
            see(ty,tx,i)

    # 현재 케이스에서 단 한 번도 학생을 만난적이 없다면
    if triger == 'OFF':
        poss = 'YES'
        break

print(poss)
www.acmicpc.net/problem/18428