사이트 #18428 감시 피하기:BFS/ 난이도

🚩플로우 (선택)

코드를 풀이할 때 적었던 플로우가 있나요?

• 1차 플로우

  • X (빈 공간) 의 좌표 empy_p에 넣기
  • T의 위치를 통해 해당 graph에서 True/ false 판단
  • 그 뒤는 .. 잘 모르겠음

• 2차 플로우 ( 풀이 과정 확인 후)

  필요한 함수

  1. 장애물 설치 함수 - #backtraking , #재귀
  2. T의 상하좌우 감시 시야에 S 존재 여부 확인 함수 - #bfs,# 사실 dfs일듯?

  1. T의 위치 와 graph 행렬 입력 받기
  2. backtracking 으로 장애물 설치 가능한 모든 위치(경우)를 탐색함
     1. 3개의 장애물 설치 완료하면 , 선생님들 위치에서 bfs 탐색으로 감시 범위에 S 가 있는지 확인한다. - > check_s
     2. 3개 장애물(O) 설치하기
        1. 모든 빈 공간(x)에 장애물 3개 설치한다
        2. 장애물 설치한 곳을 “X” → “O”로 변경
        3. 장애물 3개 설치 후 (a)과정을 통해 탐색이 끝나고 false면 “O”를 “X”로 초기화 한 후 그 다음 빈 공간에 장애물(O) 설

🚩제출한 코드

import sys
def backtracking(cnt):
    global flag

    # 3개 장애믈 설치 끝나면
    if cnt == 3 :
        # 선생님들 위치에서 감시
        if check_S():
            flag = True # 성공하면 flag를 True로 초기화
            return True
    else : # 모든 빈 공간에 장애물 3개씩 설치해보기
        for x  in range(n):
            for y in range(n) :
                if graph[x][y] == "X":
                    graph[x][y] = "O"
                    backtracking(cnt+1) # backtraking
                    graph[x][y] = "X" 
        

def check_S() : 
    #check_S : 선생님 시야 함수 (bfs -> 근데 dfs에 가깝지 않나???)
    #check = True # T가 S 를 못 찾음
    
    # 상하좌우 움직이는 배열
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    for t in teachers : # 선생님 위치에서
        
        for k in range(4): #상하좌우 탐색
            nx = t[0] + dx[k]
            ny = t[1] + dy[k]
            # 선생님 x,y 좌표
            while  0 <= nx < n and 0 <= ny < n : # graph 범위 밖 넘어가는 것 차단
                if graph[nx][ny] == "O" : #방애물 있으면 해당 방향 스킵
                    break
                if graph[nx][ny] == "S"  : # S 가 있으면 실패
                     return False
                nx += dx[k]
                ny += dy[k]

    # 모두 통과하면 S가 안보이는 것으로 성공
    return True
        

# input 받기 -  graph , T 위치 , X 위치
n = int(sys.stdin.readline())
flag = False # (답) 전체 시야 차단 yes or no  
graph = [] # 전체 MAP 위치
teachers = list () # 선생님 (T) 좌표

for i in range(n):
    graph.append(list(map(str , sys.stdin.readline().split())))
    for j in range(n):
        if graph[i][j] == "T": # 선생님 있는 좌표 저장
            teachers.append([i,j])

# BFS 
backtracking(0)

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

• 1차 시도

"""
role : 1. T , S , O 
T - 상하좌우 like 룩  
  - 장애물 막히면 뒤에 못봄

1. T 가 볼 수 있는 영역

2. 학생 위치 

3. 3개의 장애물을 통해 모든 S 가 생존하기

"""
def student_check(position, graph) :
    # T's position = [x,y]
    # [x+dx , y] , [x-dx , y] , [x,y+dy] , [x.y-dy]
    #check = True # T가 S 를 못 찾음
    x,y = position[0] , position[1]
    dn = 1
    for r in [[x+dn , y] , [x-dn , y] , [x,y+dn] , [x.y-dn]]:
         #상하좌우 
        while r[0] >= 0 or r[0] < n or r[1] >= 0 or r[1] <n : # 범위 밖으로 넘어가면 생략
            if graph[r[0]][r[1]] == "O" : #방애물 있으면 해당 방향 스킵
                break
            if graph[r[0]][r[1]] == "S"  : # S 가 있으면
                return False
            dn +=1
        dn = 0
   
    return True
        

# input 받기 
n = int(input())
graph = [[] for _ in range(n)] # 전체 MAP 위치
empty_p = list() # 빈 공간(x) 좌표 
for i in range(n):
    tmp = list(input().split())
    for j in range(n):
        if tmp[j] == "X" :
            empty_p.append([i,j])
    graph[i]= tmp
print(graph)
print(empty_p)
print("_____")

# BFS 

💡TIL

배운 점이 있다면 입력해주세요

• backtracking

  • 모든 경로 중 특정 조건을 만족한 경로(후보군)만 탐색

  • 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기(Pruning)이라고 함

  • DFS , BFS로 구현 가능 → 주로 재귀함

    • 일반적으로 DFS등으로 모든 경로 탐색 과정에서, 조건문을 통해 Nopromising 한 상황을 정의하고 , 해당 경우에는 탐색을 중지한 후(Pruning) 그 이전 으로 돌아가 다른 경우 탐색 구현
      • 백트래킹 특성으로 no proming한 경우, 이전 부모 노드로 회귀해야 함(전 단계로 거슬러 올라감) → DFS 가 더 편
    • 탐색에서 순환(cycle)이 발생할 수 있다면 bfs 이용하는 것이 편함

  • 최적화문제, 결정 문제를 푸는데 도움

  • 관련 용어

    • 유망함(Promosing) : 진행 중인 경로가 해답을 찾을 가능성이 있을때
    • 유망하지 않음 (Nopromising) : 진행 중인 경로가 해답을 찾을 가능성이 없을때
    • 가지치기 (Pruning) : 유망하지 않은 하위 트리를 잘라냄 → 즉 유망하지 않음으로 판단 시 그 노드르이 이전( 부모)노 드로 돌아가서 다음 자식 노드로

    a + b + c + d = 20 을 만족하는 두 수를 모두 찾아내시오. ( 0 ≤ a ,b ,c ,d < 100) "

    백트래킹 : a > 20 이거나 b > 20, c > 20, d > 20 일 경우는 탐색하지 않는다

  • backtraking vs dfs

    • dfs : 재귀, stack을 이용해 탐색을 시작

      • **모든 경로(후보)**를 깊이 우선으로 탐색

    • 백트래킹 : 재귀로 탐색 시작
      • 탐색하는 길이 더 이상 조건에 맞지 않다고 판단하면 되돌아오는 것을 의미
      • for문 보다 빠르게 해결 가

    → 백트래킹 중 하나가 DFS

    bfs dfs : 완전 탐색 기

• 그래프 문제에서 bfs
  • 상하좌우 = 인접 노드로 생각하고 탐색

3x3 행렬 선택 게임

아래와 같은 행렬이 존재할 때 3개의 숫자를 선택하는 게임이다. 단, 선택한 숫자들의 행과 열은 모두 중복하면 안된다. 가장 적은 점수를 얻는 것이 승리하는 것이라 할때 선택해야하는 숫자 3개를 골라보자.

• 한정 조건 : '행과열이 달라야 한다.'

• 한정 조건 적용 후 dfs 탐색 진

• 전체 탐색 dfs

• backtraking 적용

import sys

li = [[1,5,3],[2,5,7],[5,3,5]]
chk = [False]*3
m = sys.maxsize

def backtracking(row, score):
	if row == 4: # 재귀함수를 마치는 조건
		if score < m:
			return
	for i in range(1,4):
		if chk[i] == false: # 백트래킹에서의 한정조건
			chk[i] = true
			backtracking(row+1, score + li[row][i])
			chk[i] = false
	return 

backtracking(1,0)
print(m)