백준 18428번: 감시 피하기 파이썬

1. 일단은 백트래킹으로 풀어야한다 왜냐하면 모든 위치를 탐색해야 하기 때문이다.
2. 3개의 장애물을 설치해야한다

---

막혔던 부분 백트래킹으로 X로 비어있는곳에 3개의 O를 넣는건 했다. 

하지만 어떻게 구현의 해야 선생님의 위치에서 학생의 감시를 피할수있는것을 구현 하지 못했다.

30분 고민끝에 그냥 답을 보기로 했다.

 

N = int(input())

board = [list(input().split()) for i in range(N)]

arr = []



def fun():
    for y,x in arr:
        for i in range(0,N):
            if board[y][i] == "T" or board[i][x] == "T":
                return False

    return True


def dfs(y,x,c):
    if c == 3:
        if fun():
            exit()
        return 
    
    for i in range(y,N):
        for j in range(x,N):
            if board[i][j] == "X":
                board[i][j] = "O"
                arr.append([i.j])
                if i / (N-1) == 1:
                    dfs(i+1,0,c+1)
                else :
                    dfs(i,j+1,c+1)
                arr.pop()
                board[i][j] = "X"

dfs(0,0,0)

print("NO")

전에 짠 코드다 저기서 보면 선생님의 감시를 피할수 있는 학생을 찾아내는 코드를 구현하지 못한게 보인다. 

저때는 그냥 학생 자리의 가로 세로에 그냥 선생이 있는지 찾는 코드인데 저렇게 짜면 안된다.

그래서 https://fre2-dom.tistory.com/436를 보면 된다.

[baekjoon] 백준 18428번(파이썬): 감시 피하기

---

 

import sys

def backTracking(cnt):

    global flag

    # 3개의 장애물을 설치했다면

    if cnt == 3:

        # 선생님의 위치에서 감시를 한다.

        if bfs():

            flag = True # 성공했다면 flag를 true로 초기화

            return

    else:

        # 모든 빈공간에 장애물을 3개씩 설치해본다.

        for x in range(n):

            for y in range(n):

                if graph[x][y] == "X":

                    graph[x][y] = "O"

                    backTracking(cnt + 1) # backTracking

                    graph[x][y] = "X"

# bfs를 통해 감시

def bfs():

    dx = [1, -1, 0, 0]

    dy = [0, 0, 1, -1]

    for t in teacher:# 선생님의 위치에서

        for k in range(4): # 상/하/좌/우 탐색

            nx, ny = t

            while 0 <= nx < n and 0 <= ny < n:

                if graph[nx][ny] == "O":

                    break

                # 학생이 보이면 실패

                if graph[nx][ny] == "S":

                    return False

                nx += dx[k]

                ny += dy[k]

    # 모두 통과하면 학생이 안보이는 것으로 성공

    return True

n = int(sys.stdin.readline())

flag = False

graph = []

teacher = []

# 반복문을 통해 복도 정보를 입력 받는다.

for i in range(n):

    graph.append(list(map(str, sys.stdin.readline().split())))

    for j in range(n):

        if graph[i][j] == "T": # 선생님이 있는 좌표를 저장

            teacher.append([i, j])

backTracking(0)

if flag:

    print("YES")

else:

    print("NO")

 

---

문제를 답보고 풀면서 깨달은점 막상 답보면 쉬운데 아쉽다 다음에 좀더 고민해야겠다.

그럼 BYE