감시피하기

https://www.acmicpc.net/problem/18428

18428번: 감시 피하기

문제요약:

학생과 선생이 있을때 중간에 3개의 벽의 놓아 감시를 피할수 있는지 없는지 알아내라

골드5

 

소요시간:

55분

 

1차시도:

import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10000)

n = int(input())

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

#장애물 설치 
num = 0
piv =0
def make_wall(j,arr):
	global num
	global piv
	if piv: #한번이라도 성공했다면 그이후에 돌려놓은 함수들 다 끝
		return 
	if num==3:
		if watch(): #벽설치가 완료되었다면 확인해보기
			piv =1
			print('YES')
		return 
		
	for i in range(j,n**2): #벽설치를 효율적으로 하기 하나 설치하면 그뒤에서부터 설치가능
		if arr[i//n][i%n]=='X':
			num+=1
			arr[i//n][i%n] = 'O'
			make_wall(i,arr)
			num-=1
			arr[i//n][i%n] = 'X'
			
#find teacher			
teacher = []
for y in range(n):
	for x in range(n):
		if arr[y][x] =='T':
			teacher.append((y,x))
			
dy = [-1,0,1,0]
dx = [0,1,0,-1]

	
def watch():	#한맵에 대하여 선생이 볼 수 있는 모든 경우 보기
	for ky,kx in teacher:
		for i in range(4):
			y = ky
			x = kx
			while True:
				ny = y +dy[i]
				nx = x +dx[i]
				if 0>ny or ny>=n or nx<0 or nx>=n or arr[ny][nx]== 'O': #이걸 구현을 안했었다...
					break
				if arr[ny][nx]== 'S':
					return 0 #학생을 만났다면 더볼필요도 없이 실패
				y = ny
				x = nx
	return 1	 #학생을 안만났으므로 성공

	
make_wall(0,arr)
if not piv:
	print('NO')

 

저번 벽설치 문제 이후라 이제 n개의 벽을 효율적으로 설치하는 법을 알아 구현했고, 다만 이번문제에선 크기가 굉장히 한정적이었기 때문에, itertools를 써도 무방했다.

또한 한 완성된(벽이 모두 설치된) 맵에서 한번이라도 학생을 만났다면 실패 모든경우에서 학생과 마주친적이 없으면 성공이고 성공이라면 다른경우를 할 필요가 없기 때문에 이 논리구조가 조금 헷갈렸어서 해맸지만 그래도 시간내에 해결했다. 다시 풀어서 30분이내에 구현을해봐야 할 필요가 있는 문제 인것같다.    

아 그리고 어디서 많이 해맸는가 생각해봤더니 테두리를 넘어가는것 뿐아니라, 벽을만났을때 멈췄어야 했는데 벽만났을때 멈추는것을 구현을 안했었다... 기본에 충실하자.