• 백준18428번
• 책 351p

문제

조건

• 조건
  • 2초 / 256MB
• 입력
  • 첫째줄 : 자연수 N (3<=N<=6)
  • 둘째줄 : N줄에 걸쳐 공백으로 구분하는 복도의 정보 주어짐
    학생 = S, 선생님=T, 아무것도존재하지않으면=X
    항상 빈칸의 갯수는 3개 이상으로 주어짐
• 출력
  • 첫째줄 : 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지 여부 ("YES" or "NO")

상황

• 선생님은 상하좌우 4방향으로 장애물로 가로막히기 전까지 볼 수 있음
• 복도에 장애물이 있으면 장애물 볼 수없음
• 목표 : 복도의 빈칸 중 장애물 설치할 위치 골라, 정확히 3개 설치하여 모든 학생이 선생님의 감시로부터 피할 수있어야
• 가능 여부 출력하시오

풀이

처음 든 생각

• BFS 생각없이 봤을때
  1. 선생님의 상하좌우를 다 체크해서 학생에게 닿는 면 체크
  2. 닿는 면에서 확장시켜서, 겹치는 부분 있다면 거기에 장애물 세우기
  3. 겹치는 부분 확인 다 해도, 없다면 상하좌우에 체크한 아무데나 체크하기

• BFS로 생각했을때
  1. 모든 경우 탐색하되, BFS로 탐색하나?

시간복잡도

복도의 크기는 N*N. (N<=6)
그러므로 장애물을 3개 설치하는 최악의 조합의 수는 $_{36}C_3$
10,000 이하이므로 시간초과없이 해결 가능

정답풀이

• 장애물을 3개 설치하는 모든 경우를 확인
  • 매 경우마다 모든 학생을 감시로부터 피할 수 있는지 여부 출력해야
• 결론
  • 방법1 :모든 조합을 찾기위해 DFS/BFS 이용해 모든 조합을 반환하는 함수 작성하거나
  • 방법2 : 파이썬 조합 라이브러리 사용

파이썬 조합 라이브러리

1개 리스트에서의 조합 : combination / 2개 이상 리스트에서의 조합 : product

이외 iterator 라이브러리의 유용한 함수들

코드

from itertools import combinations

n = int(input()) # 복도의 크기
board = [] # 복도의 정보 (N*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] == '0' : # 장애물이 있는 경우
				return False
			y -= 1
	# 오른쪽방향으로 감시
	if direction == 1 :
		while y < n:
			if board[x][y] == 'S' : # 학생이 있는 경우
				return True
			if board[x][y] == '0' : # 장애물이 있는 경우
				return False
			y += 1
	# 위쪽방향으로 감시
	if direction == 2 :
		while x >= 0 :
			if board[x][y] == 'S' : # 학생이 있는 경우
				return True
			if board[x][y] == '0' : # 장애물이 있는 경우
				return False
			x -= 1
	# 아래쪽 방향으로 감시
	if direction == 3 :
		while x < n :
			if board[x][y] == 'S' : # 학생이 있는 경우
				return True
			if board[x][y] == '0' : # 장애물이 있는 경우
				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) : # spaces C 3 의 조합 리슽를 리턴한다
	# 장애물 설치해보기
	for x, y in data :
		board[x][y] = '0'
	# 학생이 한명도 감지되지 않는 경우
	if not process() :
		# 원하는 경우를 발견한거임
		find = True
		break
	# 설치된 장애물을 다시 없애기
	for x,y in data:
		board[x][y] = 'X'

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

느낀점

오잉 이거 부르트포스 아입니까