[백준: Python] 18428 - 감시 피하기

[문제]

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

백트래킹과 BFS가 조합된 문제입니다.

 

백트래킹을 통해 3개의 벽을 설치할 수 있는 경우의 수를 만들고, 모든 벽을 쌓았을 때 선생님이 학생들을 모두 찾아낼 수 있는지 확인하면 되겠습니다.

---

[초기화]

    def __init__(self):
        self.n = int(input())
        self.grid = [input().split() for _ in range(self.n)]
        self.directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        self.teacher_pos = [[i, j] for j in range(self.n) for i in range(self.n) if self.grid[i][j] == 'T']
        self.answer = 'NO'

편의를 위해 선생님들의 위치를 미리 받아놓습니다.

---

[풀이]

    def bfs(self):
        for pos in self.teacher_pos:
            for d in self.directions:
                y, x = pos

                while 0 <= y < self.n and 0 <= x < self.n:
                    if self.grid[y][x] == 'O':  # 벽을 만나면 더 이상 탐색할 수 없음
                        break
                    if self.grid[y][x] == 'S':  # 학생을 만나면 해당 벽 조합은 실패
                        return False
                    y += d[0]
                    x += d[1]

        return True

선생님들의 위치를 바탕으로 동서남북에 대한 가시거리를 한 칸씩 늘려가며 확인합니다.

• 가시거리 내
  • 벽이 있다면 확인 종료
  • 학생이 있다면 해당 벽의 조합은 실패

벽을 만나 확인이 종료되면, 그 이후에는 학생들을 숨길 수 있다는 것을 의미하므로 True를 반환합니다.

    def dfs(self, found_wall):
        if found_wall == 3:  # 모든 벽을 다 설치했다면
            if self.bfs():
                self.answer = 'YES'
            return
        for i in range(self.n):
            for j in range(self.n):
                if self.grid[i][j] == 'X':
                    self.grid[i][j] = 'O'
                    self.dfs(found_wall + 1)
                    self.grid[i][j] = 'X'

모든 좌표를 순회하며 벽을 놓을 수 있다면, 벽을 설치합니다.

 

3개의 벽 설치가 완료됐다면, 유효한 설치인지 BFS를 통해 확인합니다.

 

이 때, BFS의 결과가 True이면 Yes를 출력하고 메서드를 종료합니다.

---

[전체 코드]

class Main:
    def __init__(self):
        self.n = int(input())
        self.grid = [input().split() for _ in range(self.n)]
        self.directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        self.teacher_pos = [[i, j] for j in range(self.n) for i in range(self.n) if self.grid[i][j] == 'T']
        self.answer = 'NO'

    def dfs(self, found_wall):
        if found_wall == 3:  # 모든 벽을 다 설치했다면
            if self.bfs():
                self.answer = 'YES'
            return
        for i in range(self.n):
            for j in range(self.n):
                if self.grid[i][j] == 'X':
                    self.grid[i][j] = 'O'
                    self.dfs(found_wall + 1)
                    self.grid[i][j] = 'X'

    def bfs(self):
        for pos in self.teacher_pos:
            for d in self.directions:
                y, x = pos

                while 0 <= y < self.n and 0 <= x < self.n:
                    if self.grid[y][x] == 'O':  # 벽을 만나면 더 이상 탐색할 수 없음
                        break
                    if self.grid[y][x] == 'S':  # 학생을 만나면 해당 벽 조합은 실패
                        return False
                    y += d[0]
                    x += d[1]

        return True

    def solve(self):
        self.dfs(0)
        print(self.answer)


problem = Main()
problem.solve()

---