[이코테/dfs/백준] 감시 피하기(정답,풀이)

문제

18428번: 감시 피하기

내 정답

============================= [ 1 ] =====================================
from itertools import combinations
from collections import deque
n = int(input())
ground = []
ts, cs = [],[]
for i in range(n):
    data = list(input().split())
    for j in range(len(data)):
        if data[j] == 'X':
            cs.append((i,j))
        elif data[j] == 'T':
            ts.append((i,j)) 
    ground.append(data) 
    
dx = [0,0,-1,1]
dy = [-1,1,0,0] 

============================= [ 2 ] =====================================
# 1. 한 방향으로 학생이 보이는 지 체크하는 함수
def check(x,y,d):
    #특정 좌표와 방향을 받아 그 방향의 끝까지 검사.
    while True:
        nx = x + dx[d]
        ny = y + dy[d] 

        if nx < 0 or n <= nx or ny < 0 or n <= ny or ground[nx][ny] == 'O': # 못찾은 경우
            return False
    
        if ground[nx][ny] == "S":
            return True # 4방향을 모두 검사해야하기 때문에 하나라도 실패가나오면 체크해야함
        
        x,y = nx,ny

============================= [ 3 ] =====================================
# 2. 장애물을 세우는 경우의 수 마다 모든 선생님의 위치에서 확인
def process():
    for i in ts: # 모든 선생님에 대해 
            x,y = i
            for d in range(4): # 한선생님의 네 방향 검사. 
                if check(x,y,d): # 한 방향의 검사에서 학생을 발견했다면 T, 아니면 F
                    return True # 발견했음
    return False # 발견하지 못했음

============================= [ 4 ] =====================================
# 3. 장애물세우는 함수
def dfs():
    global find
    for com in list(combinations(cs,3)):
        # 3개를 골라 장애물을 세움
        for a,b in com:  
            ground[a][b] = 'O'

        # 로직수행
        if not process(): # 참이라면  
            return 'YES' 
        
                    
        # 다음 3개를 고르는 경우의 수를 진행하기 위해 장애물 원상복구           
        for a,b in com:
            ground[a][b] = 'X'  
    
    return 'NO'
 
print(dfs())

 

풀이

전체 풀이 흐름

특정 선생님이 상하좌우로 맵의 끝까지 확인할 수 있고, 그 사이에 장애물이 있다면 장애물 뒤의 학생은 볼 수 없다

→ 선생님의 좌표를 x, y라고 했을 때, 장애물을 만나거나 맵의 범위를 벗어날 때 까지 각각 한방향으로 (오른쪽으로 x +1 , 왼쪽으로 x-1 , 위로 y+1, 아래로 y-1 ) 진행하며 학생이 보이면 정답을 찾는 데 실패한 것으로 보고 다음 경우의 수를 찾음

 

이 과정을 세 가지 구조로 나누어 코드를 작성했다.

 

1. 장애물 배치

2. 모든 선생님을 돌아가면서 확인

3. 각각의 한 선생님이 볼 수 있는 네 방향 확인

 

 

---

중요 함수 설명

1. 입력받을 때 빈 칸과 선생님의 위치 좌표를 별도의 리스트에 따로 저장

 

2. dfs() : 빈 칸중 임의의 3칸을 뽑아 장애물을 배치하는 경우의 수 생성 후 학생을 확인하는 작업 진행. 만약 학생이 발견되어 False를 리턴받았다면 다시 다음 장애물을 세우는 경우의 수를 진행하기 위해 장애물을 원상복구시킴

(여기서 deepcopy()를 사용해 매 반복마다 리스트를 복사하는 방법을 써도 되지만 전체 리스트의 사이즈가 커질수록 메모리가 많이 소모되기 때문에 원본배열을 사용해 수정/복원시키는게 더 효율적임)

 

3. process() : 각 경우의 수 마다 선생님들의 위치를 저장한 배열을 가져와 모든 선생님의 위치에서 각 방향으로의 check함수를 호출해 학생이 발견되지 않는지 확인. 만약 발견되지 않았다면 False를 리턴

 

4. check () : 한 선생님의 한 방향에 대해서 맵 끝까지 확인했을 때 or 장애물이 발견될 때 까지 학생이 발견되지 않았는지 확인. 발견되지 않았다면False 리턴.

 

 

 

 

참고

이것이 취업을 위한 코딩테스트다(with.python)