20_감시 피하기

18428번: 감시 피하기

 

장애물을 정확히 3개 설치할 수 있는 경우의 수를 모두 찾아서, 감시를 피할 수 있는 경우가 있는 경우

YES를 출력하고, 그렇지 않은 경우 NO를 출력하면되는 문제다.

 

문제 구현을 위한 아이디어 생각은 금방했다.

1. 장애물을 설치한 후, 감시를 피할 수 있는지 여부를 확인하기 위한 함수

2. 장애물을 설치하는 함수

이 2가지 함수만 있다면 쉽게 풀 수 있는 문제라고 생각했다.

 

1번 함수는 금방 구현했으나, 문제는 2번이었다.

단순히 파이썬 itertools 패키지의 combinations 클래스를 활용하면 풀 수 있었지만, 이번에는 백트래킹을 사용해서 문제를 풀고 싶었다.

그래서 백트래킹을 사용해서 문제를 해결하려고 시도했지만 실패했다.

백트래킹을 사용해서 문제를 푼 경험이 없었기 때문에, 재귀를 어떤 식으로 구현해야 할지 감이 잡히지 않았다.

 

그래서 결국 풀이 코드를 봤다.

 

---

풀이 코드

# 18428번: 감시 피하기
import sys, copy
sys.setrecursionlimit(10**6)


# 장애물이 3개 설치된 해당 복도에서 
# 모든 학생들이 선생님의 감시를 피할 수 있는지 여부를 리턴하는 함수
def check():
    for t in teacher:
        teacher_x, teacher_y = t[0], t[1]
        # 상
        for i in range(teacher_x - 1, -1, -1):
            if graph[i][teacher_y] == 'O':
                break
            if graph[i][teacher_y] == 'S':
                return False
        # 하
        for i in range(teacher_x + 1, n):
            if graph[i][teacher_y] == 'O':
                break
            if graph[i][teacher_y] == 'S':
                return False
        # 좌
        for j in range(teacher_y - 1, -1, -1):
            if graph[teacher_x][j] == 'O':
                break
            if graph[teacher_x][j] == 'S':
                return False
        # 우
        for j in range(teacher_y + 1, n):
            if graph[teacher_x][j] == 'O':
                break
            if graph[teacher_x][j] == 'S':
                return False
    return True



# 장애물 설치 -> 백트래킹
def back_tracking(cnt):
    global answer
    if cnt == 3:
        if check():
            answer = True
            return
    else:
        for i in range(n):
            for j in range(n):
                if graph[i][j] == 'X':
                    graph[i][j] = 'O'
                    back_tracking(cnt + 1)
                    graph[i][j] = 'X'

n = int(input()) # 복도 크기
graph = [] # 복도
teacher = [] # 선생님의 좌표를 저장하는 리스트
answer = False # 이게 True면 Yes 출력, 아니면 No 출력

for i in range(n):
    row = list(input().split())
    graph.append(row)
    for j in range(n):
        if graph[i][j] == "T":
            teacher.append((i, j))


back_tracking(0)

if answer:
    print("YES")
else:
    print("NO")

 

 

 

핵심이 되는 코드는 이 부분이다.

# 장애물 설치 -> 백트래킹
def back_tracking(cnt):
    global answer
    if cnt == 3:
        if check():
            answer = True
            return
    else:
        for i in range(n):
            for j in range(n):
                if graph[i][j] == 'X':
                    graph[i][j] = 'O'
                    back_tracking(cnt + 1)
                    graph[i][j] = 'X'

 

back_tracking이라는 함수를 통해 재귀를 돈다.

장애물이 3개 설치되었을 때가 종료조건이다.

3개 설치되었을 때는 check 함수를 통해 감시를 피할 수 있는지 확인하고, 감시를 피할 수 있는 경우가 발견되면,

백트래킹을 중단한다.

만약 장애물이 3개 설치되지 않은 경우는 for문을 통해 빈 공간일 경우 장애물을 설치하는 방식으로 구현한다.

그리고 for문 내부에서 다시 back_tracking함수를 호출한다. back_tracking함수를 나온 후에는 해당 칸을 다시 빈 복도로 만들어버린다.

 

기본적으로 백트래킹은 이런 식으로 구현하는 것 같다.

계속 풀면서 익숙해지자.