백준 / 감시 피하기 / 18428번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 감시 피하기 / 18428번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/18428

 

문제 설명

---

나의 풀이

move = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 상 하 좌 우 움직임


# 4방향으로 부딪치는지 확인하는 함수
def search(ty, tx, arr):
    for dy, dx in move:
        cy, cx = ty, tx
        while True:
            cy += dy
            cx += dx
            if cy < 0 or cy >= len(arr) or cx < 0 or cx >= len(arr):
                break
            if arr[cy][cx] == 'O':  # 벽
                break
            if arr[cy][cx] == 'S':  # 학생 발견
                return True
    return False  # 모든 방향에서 학생 없음


def solution(arr, N):
    answer = ["NO"]
    t_location = []

    # 선생님 위치 확인
    for iy in range(N):
        for ix in range(N):
            if arr[iy][ix] == 'T':
                t_location.append((iy, ix))

    def wall(count):
        if count == 3:
            for ty, tx in t_location:
                if search(ty, tx, arr):
                    return
            answer[0] = "YES"
            return
        
        for iy in range(N):
            for ix in range(N):
                if arr[iy][ix] == 'X':
                    arr[iy][ix] = 'O'
                    wall(count + 1)
                    arr[iy][ix] = 'X'
                    if answer[0] == 'YES':
                        return

    wall(0)
    return answer[0]


if __name__=="__main__":
    N = int(input())
    school = [list(map(str, input().split())) for _ in range(N)]

    print(solution(school, N))
    """
    print(solution([['X', 'S', 'X', 'X', 'T'],
                    ['T', 'X', 'S', 'X', 'X'],
                    ['X', 'X', 'X', 'X', 'X'],
                    ['X', 'T', 'X', 'X', 'X'],
                    ['X', 'X', 'T', 'X', 'X']], 5))
    """

---

※ 알아야 할 것

백트래킹을 배울 수 있는 아주 좋은 문제인 것 같습니다!!!

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

13459번: 구슬 탈출이랑 비슷한 문제입니다!