[DFS/BFS] 감시 피하기 (BAEKJOON - 18428)

1. 문제

T는 선생님 S는 학생

벽(W) 3개를 세워서 감시를 피할 수 있으면 YES를 출력, 아니면 NO 출력

 

2. 입력

# SET - 1
5
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

# SET -2
4
S S S T
X X X X
X X X X
T T T X

 

3. 출력

# SET - 1
YES

# SET - 2
NO

 

4. 풀이

N이 3~6으로 맵 크기가 작기 때문에 완전탐색도 가능하다.

선생님의 감시를 피할 수 있는지 확인하는 부분이 조금 다를 뿐

 

벽을 세우면서 (dfs를 돌리면서)

벽이 3개일 때, 선생님의 감시를 피할 수 있는지 체크

 

여기서 가능하다면 최종적으로 True를 들고가면된다.

 

지금은 풀이가 잘 이해되는데 다른거 공부하다가 까먹을까봐 기록합니당...

 

5. 코드

N = int(input())
data = []
teachers = []
for i in range(N):
    data.append(list(input().split()))
    for j, v in enumerate(data[i]):
        if v == 'T':
            teachers.append((i,j))

FOUR_DIR = [(0,1), (1,0), (0,-1), (-1,0)]

temp = [['X'] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        temp[i][j] = data[i][j]

answer = False

def dfs(count, temp):
    global answer
    if count == 3:
        s_count = 3
        for ti, tj in teachers:
            for dx, dy in FOUR_DIR:
                nx, ny = ti+dx, tj+dy
                while nx >= 0 and nx < N and ny >= 0 and ny < N:
                    if temp[nx][ny] == 'W':
                        break
                    if temp[nx][ny] == 'S':
                        s_count -= 1
                        return
                    nx+=dx
                    ny+=dy
        if s_count == 3:
            answer = True
    else:
        for i in range(N):
            for j in range(N):
                if temp[i][j] == 'X':
                    temp[i][j] = 'W'
                    dfs(count+1, temp)
                    temp[i][j] = 'X'

dfs(0, data)

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