[이.취.코] [백준] Chap 13. BFS_DFS - Q20. 감시 피하기

@mildsalmon·2021-09-25 10:21

1. 감시 피하기

난이도
- 중상
풀이 시간
- 60분
시간 제한
- 2초
메모리 제한
- 256 MB
출처
- 18428번: 감시 피하기 (acmicpc.net)

A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 내 답안

a. 1차 시도 (성공 / 코드가 더럽고, 주석이 없어서인지 가독성이 떨어짐)


def dfs(x, y, graph, d):
    global n

    if 0 <= x < n and 0 <= y < n:
        if graph[x][y] == 'X':
            dx = x + d[0]
            dy = y + d[1]

            result = dfs(dx, dy, graph, d)
            return result

        elif graph[x][y] == 'O':
            return False
        elif graph[x][y] == 'S':
            return True
    return False

def recursive(graph, count):
    global n, teacher, student, ds

    if count == 3:
        result = []
        for t in teacher:
            for d in ds:
                dx = t[0] + d[0]
                dy = t[1] + d[1]

                result.append(dfs(dx, dy, graph, d))

        if True not in result:
            return 'YES'
        else:
            return 'NO'

        # for i in range(n):
        #     for j in range(n):
        #         if graph[i][j] == 'T':
        #
    else:
        for i in range(n):
            for j in range(n):
                if graph[i][j] == 'X':
                    count += 1
                    graph[i][j] = 'O'
                    answer = recursive(graph, count)
                    if answer == 'YES':
                        return 'YES'
                    count -= 1
                    graph[i][j] = 'X'
        return 'NO'

global n, teacher, student, ds

n = int(input())

student = []
teacher = []

graph = []

ds = ((1, 0), (-1, 0), (0, 1), (0, -1))

for i in range(n):
    temp = list(input().split())
    graph.append(temp)
    for j in range(len(temp)):
        if temp[j] == "S":
            student.append([i, j])
        elif temp[j] == "T":
            teacher.append([i, j])

# print(*student, sep='\n')
# print()
# print(*teacher, sep='\n')
# print(*graph, sep='\n')

answer = recursive(graph, 0)

print(answer)

# 31분 / Pass

b. 2차 시도 (성공 / 코드 개선, 가독성 향상)


def dfs(x, y, array, d):
    global N

    dx = x + d[0]
    dy = y + d[1]

    if 0 <= dx < N and 0 <= dy < N:
        if array[dx][dy] == 'X':
            result = dfs(dx, dy, array, d)

            return result
        # 장애물을 만나서 학생을 찾지 못했다.
        elif array[dx][dy] == 'O':
            return True
        # 학생을 찾았다.
        elif array[dx][dy] == 'S':
            return False
    # 범위를 벗어나서 학생을 찾지 못했다.
    return True

def recursive(count, array):
    global N, teacher
    # 장애물 3개 설치 완료
    if count == 3:
        ds = ((0, 1), (1, 0), (0, -1), (-1, 0))

        for t in teacher:
            x, y = t
            for d in ds:
                result = dfs(x, y, array, d)
                # 학생을 발견했을 경우
                # 더 이상 탐색은 무의미하기 때문에, 장애물을 재배치함.
                if not result:
                    return False
        # 선생님이 모든 방향을 탐색했는데, 학생이 발견되지 않았을 경우
        return True
    # 장애물 3개 설치 미완료
    elif count != 3:
        for i in range(N):
            for j in range(N):
                # 장애물도 학생도 없는 칸이라면,
                # 장애물을 설치할 수 있다면. 
                if array[i][j] == 'X':
                    count += 1
                    array[i][j] = 'O'

                    answer = recursive(count, array)

                    if answer:
                        return True

                    array[i][j] = 'X'
                    count -= 1
        return False

global N, teacher

N = int(input())

array = []
teacher = []

for i in range(N):
    temp = list(input().split())
    array.append(temp)

    for j in range(len(temp)):
        if temp[j] == 'T':
            teacher.append((i, j))

answer = recursive(0, array)

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

c. 회고

내 풀이

이전에 풀었던 문제(연구소)랑 비슷한 유형인 것 같아서 그냥 풀었다.
2차원 리스트를 3단계 재귀로 진입하는 문제 !
조합을 썻으면 더 편하게 풀었을지도 모르겠다

C. 문제 해설

이해한 내용을 바탕으로 작성했습니다.

지금까지 풀어봤던 DFS문제랑은 푸는 방식이 조금 다르다. 지금까지 풀어본 문제들은 DFS를 호출할 때마다 4방향(상하좌우)를 확인해야했다. 다만 이 문제에서는 DFS를 실행할 때마다 상하좌우를 확인하는 것이 아닌 맨 처음에 실행할때만 상하좌우를 확인하고 그 후부터는 장애물이나 학생을 만날때까지 같은 방향만 탐색한다.