감시 피하기 - BOJ 18428
in ALGORITHM
‘풀이시간 60분 , 시간제한 2초, 메모리제한 256MB, BOJ 18428 (취코테 346p)’
감시 피하기 - BOJ 18428
이 문제는 14502번 문제와 상당히 흡사하다. DFS를 이용하면 벽을 매번 방문했던 장소인지 확인하고 설치를 해야한다. 하지만 조합 라이브러리인 combinations를 이용하면 벽을 설치할 수 있는 모든 경우의 수를 구할 수 있으므로 중복된 곳을 확인하지 않고 해당하는 위치에만 벽을 설치하므로 훨씬 빠르게 해결할 수 있다.
DFS를 활용한 풀이
from sys import stdin
n = int(input())
yes = 0 # 감시를 실패한 선생님 수
status = False
data = []
temp = [[''] * n for _ in range(n)]
t_num = 0
for i in range(n):
data.append(list(stdin.readline().rstrip().split()))
t_num += data[i].count('T') # 선생님의 수 저장
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def surveillance(x, y):
global yes
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
while nx >= 0 and ny >= 0 and nx < n and ny < n:
if temp[nx][ny] == 'S': # 학생을 발견하면 그대로 종료
return
elif temp[nx][ny] == 'O' or temp[nx][ny] == 'T':
break # 벽이나 다른 선생님을 만난다면 다른 방향 확인
nx += dx[i] # 한 방향으로 계속 이동 (x)
ny += dy[i] # 한 방향으로 계속 이동 (y)
yes += 1
return
def dfs(count):
global yes, status
if count == 3:
for i in range(n):
for j in range(n):
temp[i][j] = data[i][j]
for i in range(n):
for j in range(n):
if temp[i][j] == 'T':
surveillance(i, j)
if yes == t_num: # 감시를 실패한 선생님의 수와 전체 선생님의 수가 같다면
status = True # 탈출 성공
yes = 0
return
else:
yes = 0
return
for i in range(n):
for j in range(n):
if data[i][j] == 'X': # 빈 자리라면
data[i][j] = 'O' # 벽을 설치
count += 1 # 벽 설치 횟수 1 증가
dfs(count) # 재귀로 설치 반복
data[i][j] = 'X' # 설치 해제
count -= 1 # 해제 후 설치 횟수 감소
dfs(0)
if status:
print("YES")
else:
print("NO")
조합 라이브러리를 이용한 풀이🤘
from itertools import combinations
from sys import stdin
n = int(input()) # 복도의 크기
board = [] # 복도 정보
teachers = [] # 선생님 위치 정보
spaces = [] # 빈 공간 위치 정보
for i in range(n):
board.append(stdin.readline().rstrip().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")
