20_감시 피하기

2024. 2. 7. 17:11· 알고리즘/이것이 코딩테스트다
728x90
 

18428번: 감시 피하기

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복

www.acmicpc.net

 

장애물을 정확히 3개 설치할 수 있는 경우의 수를 모두 찾아서, 감시를 피할 수 있는 경우가 있는 경우

YES를 출력하고, 그렇지 않은 경우 NO를 출력하면되는 문제다.

 

문제 구현을 위한 아이디어 생각은 금방했다.

1. 장애물을 설치한 후, 감시를 피할 수 있는지 여부를 확인하기 위한 함수

2. 장애물을 설치하는 함수

이 2가지 함수만 있다면 쉽게 풀 수 있는 문제라고 생각했다.

 

1번 함수는 금방 구현했으나, 문제는 2번이었다.

단순히 파이썬 itertools 패키지의 combinations 클래스를 활용하면 풀 수 있었지만, 이번에는 백트래킹을 사용해서 문제를 풀고 싶었다.

그래서 백트래킹을 사용해서 문제를 해결하려고 시도했지만 실패했다.

백트래킹을 사용해서 문제를 푼 경험이 없었기 때문에, 재귀를 어떤 식으로 구현해야 할지 감이 잡히지 않았다.

 

그래서 결국 풀이 코드를 봤다.

 


풀이 코드

# 18428번: 감시 피하기
import sys, copy
sys.setrecursionlimit(10**6)


# 장애물이 3개 설치된 해당 복도에서 
# 모든 학생들이 선생님의 감시를 피할 수 있는지 여부를 리턴하는 함수
def check():
    for t in teacher:
        teacher_x, teacher_y = t[0], t[1]
        # 상
        for i in range(teacher_x - 1, -1, -1):
            if graph[i][teacher_y] == 'O':
                break
            if graph[i][teacher_y] == 'S':
                return False
        # 하
        for i in range(teacher_x + 1, n):
            if graph[i][teacher_y] == 'O':
                break
            if graph[i][teacher_y] == 'S':
                return False
        # 좌
        for j in range(teacher_y - 1, -1, -1):
            if graph[teacher_x][j] == 'O':
                break
            if graph[teacher_x][j] == 'S':
                return False
        # 우
        for j in range(teacher_y + 1, n):
            if graph[teacher_x][j] == 'O':
                break
            if graph[teacher_x][j] == 'S':
                return False
    return True



# 장애물 설치 -> 백트래킹
def back_tracking(cnt):
    global answer
    if cnt == 3:
        if check():
            answer = True
            return
    else:
        for i in range(n):
            for j in range(n):
                if graph[i][j] == 'X':
                    graph[i][j] = 'O'
                    back_tracking(cnt + 1)
                    graph[i][j] = 'X'

n = int(input()) # 복도 크기
graph = [] # 복도
teacher = [] # 선생님의 좌표를 저장하는 리스트
answer = False # 이게 True면 Yes 출력, 아니면 No 출력

for i in range(n):
    row = list(input().split())
    graph.append(row)
    for j in range(n):
        if graph[i][j] == "T":
            teacher.append((i, j))


back_tracking(0)

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

 

 

 

핵심이 되는 코드는 이 부분이다.

# 장애물 설치 -> 백트래킹
def back_tracking(cnt):
    global answer
    if cnt == 3:
        if check():
            answer = True
            return
    else:
        for i in range(n):
            for j in range(n):
                if graph[i][j] == 'X':
                    graph[i][j] = 'O'
                    back_tracking(cnt + 1)
                    graph[i][j] = 'X'

 

back_tracking이라는 함수를 통해 재귀를 돈다.

장애물이 3개 설치되었을 때가 종료조건이다.

3개 설치되었을 때는 check 함수를 통해 감시를 피할 수 있는지 확인하고, 감시를 피할 수 있는 경우가 발견되면,

백트래킹을 중단한다.

만약 장애물이 3개 설치되지 않은 경우는 for문을 통해 빈 공간일 경우 장애물을 설치하는 방식으로 구현한다.

그리고 for문 내부에서 다시 back_tracking함수를 호출한다. back_tracking함수를 나온 후에는 해당 칸을 다시 빈 복도로 만들어버린다.

 

기본적으로 백트래킹은 이런 식으로 구현하는 것 같다.

계속 풀면서 익숙해지자.

728x90

'알고리즘 > 이것이 코딩테스트다' 카테고리의 다른 글

22_블록 이동하기  (0) 2024.02.08
21_인구 이동  (1) 2024.02.07
19_연산자 끼워넣기  (0) 2024.02.06
18_괄호 변환  (0) 2024.02.06
17_경쟁적 전염  (0) 2024.02.02
'알고리즘/이것이 코딩테스트다' 카테고리의 다른 글
  • 22_블록 이동하기
  • 21_인구 이동
  • 19_연산자 끼워넣기
  • 18_괄호 변환
happenundo
happenundo
happenundo
2023~ 개발블로그
happenundo
전체
오늘
어제
  • 분류 전체보기 (207)
    • TIL (3)
    • 알고리즘 (188)
      • 프로그래머스 (47)
      • 백준 (69)
      • 파이썬 문법 (11)
      • 이것이 코딩테스트다 (46)
      • 알고리즘 노트 (6)
      • SQL (8)
    • Spring (4)
      • Spring 입문 (2)
      • 개인 프로젝트 (1)
      • 인텔리제이 (1)
    • CS (8)
      • DB (2)
      • 네트워크 (1)
      • 그외 (5)
    • ~2022 (1)
    • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 이것이코딩테스트다
  • 동적프로그래밍
  • 이진탐색
  • 백준
  • sql
  • 우선순위큐
  • BFS
  • 다익스트라
  • 구현
  • 백트래킹
  • 괄호변환
  • DP
  • 최단거리
  • 다이나믹프로그래밍
  • 완전탐색
  • 재귀
  • deepcopy
  • 파이썬
  • 그리디
  • 스택
  • 프로그래머스
  • 큐
  • 정렬
  • dfs
  • 이코테
  • distinct
  • 플로이드워셜
  • CS
  • BinarySearch
  • 알고리즘

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
happenundo
20_감시 피하기
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.