문제 바로가기
골드 V (23.03.22 기준)
✏ 생각하기
입력 크기가 작다. 따라서 장애물을 놓을 수 있는 모든 경우의 수 각각에서 선생님들이 학생들 중 한 명이라도 관찰할 수 있는지 확인해도 충분할 것이라 생각했다.
📒 알고리즘
- 장애물을 놓을 수 있는 위치들을 구한다.
- 나는 빈 공간 전체가 아니라, 선생님과 학생이 일직선상에 위치할 때, 그 선상의 빈공간을 후보지로 등록하는 식으로 구했다. 이렇게 하면 백트래킹에 소요되는 시간을 줄일 수 있을 것이라 생각했기 때문이다. 하지만 시간 복잡도 면에서 득도 없었고 오히려 미처 고려하지 못한 경우가 있었으니..
- 백트래킹 기반의 완전탐색으로 위 후보지 중 3곳에 장애물을 설치하는 모든 경우를 탐색한다.
- 아무 선생님 자리에서 네 방향 중 한 방향이라도 학생이 관측될 경우, 그 경우는 실패
- 모든 선생님 자리에서 네 방향에서 한 번도 학생이 관측되지 않을 경우,
answer = "YES"
💻 코드
위 알고리즘을 토대로 처음 제출한 코드는 아래와 같다.
import sys
answer = "NO"
n = int(sys.stdin.readline())
hall, teacher = [], []
for i in range(n):
hall.append(list(map(str, sys.stdin.readline().split())))
for j in range(n):
if hall[i][j] == 'T':
teacher.append((i, j))
object_candidates = set()
dxs = [1, 0, -1, 0]
dys = [0, 1, 0, -1]
def student_search(y, x, dy, dx): # [dy, dx] 방향에 학생이 존재하는가 & 장애물 설치 후보지 탐색 함수
# 장애물이나 복도 끝에 다다르기 전 학생을 발견할 경우 return True, object_candidates
# 반대의 경우 return False, []
# object_candidates : 선생님이 바라보는 방향에 있는, 장애물 설치 가능한 빈 공간
temp = []
while 0 <= y+dy < n and 0 <= x+dx < n:
if hall[y+dy][x+dx] == 'S':
return True, temp
elif hall[y+dy][x+dx] == 'O':
return False, []
temp.append((y+dy, x+dx))
y += dy
x += dx
return False, []
def find_object_candidates(ty, tx): # 4방향에 대해 student_search 함수를 수행하는함수
global object_candidates
for i in range(4):
_, spaces = student_search(ty, tx, dys[i], dxs[i])
for space in spaces:
object_candidates.add(space)
for _, tloc in enumerate(teacher):
find_object_candidates(*tloc)
object_candidates = list(object_candidates)
def dfs(idx, ob_cnt): # 백트래킹 기반 3개 장애물 설치 모든 경우의 수 탐색 함수
if ob_cnt == 3:
for _, tloc in enumerate(teacher):
ty, tx = tloc
for i in range(4):
flag, _ = student_search(ty, tx, dys[i], dxs[i])
if flag: return
global answer
answer = "YES"
else:
for i in range(idx, len(object_candidates)):
oy, ox = object_candidates[i]
hall[oy][ox] = "O"
dfs(i+1, ob_cnt+1)
hall[oy][ox] = "X"
if object_candidates:
dfs(0, 0)
print(answer)결과는 틀렸다!
왜 틀렸을까? 논리적으로 찾지 못해서 잘못된 결과를 뱉어내는 input을 찾아본 결과, 다음과 같은 input이 정답과 다른 결과를 만들어내는 것을 확인했다.
3
T T T
X T T
S X X
# 정답 : "YES"
# 프로그램 결과 : "NO"이유는 내가 '장애물 설치 후보지'에 '선생님과 학생이 공존하는 일직선상의 빈공간'만을 고려했기 때문이다. 위 input에선 object_candidates에 [1, 0]만 저장되는데, 백트래킹 함수에서 ob_cnt == 3인 경우가 아예 발생하지 않아 해당 조건의 if문 안의 answer 업데이트 코드가 실행되지 않는다.
해당 문제만 해결할 수 있도록 부랴부랴 수정해서 재제출 했더니 성공할 수 있었다...
# 위 코드에서 마지막 if object_candidates 부터 아래 내용으로 대체했다.
if object_candidates:
if len(object_candidates) <= 3: # 장애물 설치는 한 가지 경우밖에 없다
for i in range(len(object_candidates)):
oy, ox = object_candidates[i]
hall[oy][ox] = "O"
flag = False
for _, tloc in enumerate(teacher):
ty, tx = tloc
for i in range(4):
flag, _ = student_search(ty, tx, dys[i], dxs[i])
if flag: break # 학생이 보였다. 불가능
if flag: break
answer = "NO" if flag else "YES"
else: dfs(0, 0)
print(answer)추한 코드다. 하지만 이 문제에 예상 시간의 2배 이상을 써버려서 빨리 끝내고 싶었다..ㅠㅠ
문제를 빨리 풀어내고 싶은 마음에 러프하게 설계한 것을 바로 코드로 옮기려고 해서 이렇게 됐다. 시간 면에서도 이득을 보려 추가했던 코드도 딱히 쓸모 없던 코드였고... 1. 코딩을 시작하기 전 항상 내 알고리즘에 논리적 허점이 없는지 침착하게, 끝까지 살펴보자! 2. 그리고 단순한 풀이가 문제 시간 제한을 초과하지 않는다면 바로 적용하도록 하자! 그렇지 않으면 오히려 놓치는 부분이 발생할 수 있다. (이번 풀이처럼..)
👀 다른 풀이
이것이 취업을 위한 코딩 테스트다 with Python (나동빈 저, 한빛미디어) 에 실린 문제로, 책에서 제시하는 정답 코드는 다음과 같다. 해당 코드에서는 장애물을 설치하는 경우의 수를 DFS/BFS로 구하지 않고, itertools의 combinations를 사용해서 구했다. 최악의 경우가 36C3인데, 이는 10,000 이하의 수이기에 완전 탐색을 수행해도 시간 초과는 발생하지 않는다.
