[백준 18428번] 감시 피하기

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

18428번: 감시 피하기

---

 

문제 유형: 브루트포스

 

풀이 과정:

DFS를 이용하여 해결 했다.

장애물의 위치는 itertools 라이브러리를 사용하여 장애물의 위치를 바꾸면서 가능,불가능을 판정함.

DFS를 이용하는 문제 중 한방향으로만 계속 가는 문제이기 때문에 초반 DFS를 실행할때 dir를 지정해주고,

계속 같은 dir으로만 DFS를 실행하는 방식으로 문제를 풀었다.

---

#백준18428
from itertools import combinations
import copy
n = int(input())
graph = [input().split() for _ in range(n)]

list_x = []

for i in range(n):
    for j in range(n):
        if graph[i][j] == 'X':
            list_x.append((i,j))

comb = list(combinations(list_x,3))

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


def dfs(x,y,dir):
    nx = x+dx[dir]
    ny = y+dy[dir]
    if nx<0 or nx>=n or ny<0 or ny>=n:
        return
    if map[nx][ny] == 'O':
        return
    if map[nx][ny] == 'S':
        global poss
        poss = False
    dfs(nx,ny,dir)

for o in comb:
    poss = True
    map = copy.deepcopy(graph)
    
    o1,o2,o3 = o[0],o[1],o[2]
    map[o1[0]][o1[1]] = 'O'
    map[o2[0]][o2[1]] = 'O'
    map[o3[0]][o3[1]] = 'O'
    for i in range(n):
        for j in range(n):
            if map[i][j] == 'T':
                for dir in range(4):
                    dfs(i,j,dir)
    if poss == True:
        print("YES")
        break
if poss == False:
    print("NO")

*처음 제출하였을 때 틀렸는데 map의 index 범위를 넘어서는 코드 처리하는 부분에서 부등호 기호를 잘못썻다...