*문제 출처는 백준에 있습니다.
문제 제목: 감시 피하기 / 18428번 (골드 5단계)
문제 사이트: https://www.acmicpc.net/problem/18428
문제 설명

나의 풀이
move = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 상 하 좌 우 움직임
# 4방향으로 부딪치는지 확인하는 함수
def search(ty, tx, arr):
for dy, dx in move:
cy, cx = ty, tx
while True:
cy += dy
cx += dx
if cy < 0 or cy >= len(arr) or cx < 0 or cx >= len(arr):
break
if arr[cy][cx] == 'O': # 벽
break
if arr[cy][cx] == 'S': # 학생 발견
return True
return False # 모든 방향에서 학생 없음
def solution(arr, N):
answer = ["NO"]
t_location = []
# 선생님 위치 확인
for iy in range(N):
for ix in range(N):
if arr[iy][ix] == 'T':
t_location.append((iy, ix))
def wall(count):
if count == 3:
for ty, tx in t_location:
if search(ty, tx, arr):
return
answer[0] = "YES"
return
for iy in range(N):
for ix in range(N):
if arr[iy][ix] == 'X':
arr[iy][ix] = 'O'
wall(count + 1)
arr[iy][ix] = 'X'
if answer[0] == 'YES':
return
wall(0)
return answer[0]
if __name__=="__main__":
N = int(input())
school = [list(map(str, input().split())) for _ in range(N)]
print(solution(school, N))
"""
print(solution([['X', 'S', 'X', 'X', 'T'],
['T', 'X', 'S', 'X', 'X'],
['X', 'X', 'X', 'X', 'X'],
['X', 'T', 'X', 'X', 'X'],
['X', 'X', 'T', 'X', 'X']], 5))
"""

※ 알아야 할 것
백트래킹을 배울 수 있는 아주 좋은 문제인 것 같습니다!!!
https://www.acmicpc.net/problem/13459
13459번: 구슬 탈출이랑 비슷한 문제입니다!
'Coding Test > 백준-Python' 카테고리의 다른 글
| 백준 / 오아시스 재결합 / 3015번 / Python (0) | 2025.10.29 |
|---|---|
| 백준 / 돌 던지기 / 3025번 / Python (0) | 2025.10.28 |
| 백준 / 카잉 달력 / 6064번 / Python (0) | 2025.10.16 |
| 백준 / 전기 요금 / 5710번 / Python (0) | 2025.10.16 |
| 백준 / 안녕 / 1535번 / Python (0) | 2025.10.14 |