[백준 python] 18428번 감시 피하기
레벨: 실버 1
언어: python
📑풀이 과정
이 문제는 14502번 연구소 문제와 비슷하다고 생각하여 그러한 방식으로 풀이를 접근했다.
이 문제를 풀기 위해서는 크게 2가지가 필요하다.
- 장애물을 설치하는 함수
- 선생의 상하좌우 일직선으로 학생이 있는지 확인하는 함수
1번 함수(solution(count))
solution 함수는 벽을 설치할 수 있는 모든 경우를 찾는 함수이다.
1번의 함수는 재귀방식을 사용하여 X가 되어 있는 곳을 찾고 'O'로 바꿔준다. 그리고 count를 1증가 시킨 후 다시 함수를 호출한다.
이렇게 했을때 count 3 즉 벽이 3개가 설치 되었을 때 check_S(감시하는 함수)를 실행하여 준다.
그리고 check_S(감시하는 함수)가 끝나면 함수를 종료하고 'O'로 바꾼 곳을 다시 'X'로 변경한다.
위 과정을 장애물을 설치할 수 있는 모든 경우에 실행시켜준다.
2번 함수(check_S)
2번 함수는 선생(T)의 위치에서 상,하,좌,우 일직선으로 학생이 있는지 확인하는 함수이다.
학생이 있어 감시가 가능하면 True
상하좌우 직선상에 학생이 없다면 False를 리턴한다.
for 문으로 상하좌우 움직일 위치를 nx, ny에 좌표값 계산한다.
x,y 가 (0,0) 이면 for문에서 우: (1,0), 좌: (-1,0), 상: (0,1), 하(0,-1)로 움직인다.
그리고 while문을 사용하여 좌표계를 벗어나거나 장애물이 없을 때는
같은 방향으로 계속 이동하게 한다.
이동을 하다가 학생('S')를 만나게 되면 True를 리턴한다.
모든 방향을 확인하고 학생을 만나지 않았다면 False를 리턴한다.
학생을 감시할 수 없는 선생의 수를 count하여 모든 선생이 감시를 할 수 없을 때를 찾는다.
📋풀이 코드
n = int(input())
graph = []
teacher = 0
for _ in range(n):
data = list(input().strip().split(' '))
teacher += data.count('T')
graph.append(data)
# 상,하,좌,우 움직이는 배열
dx = [1,-1, 0, 0]
dy = [0, 0, 1, -1]
# 직선 방향 확인 함수
def check_S(x,y):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 직선 방향으로 확인
while 0<= nx < n and 0<= ny < n and graph[nx][ny] !='O':
if graph[nx][ny] == 'S':
# 감시가능하다
return True
else:
# T 나 X으면 계속 탐색
nx += dx[i]
ny += dy[i]
# 감시 불가능하다
return False
def solution(count):
global answer
if count == 3:
cnt = 0
for i in range(n):
for j in range(n):
if graph[i][j] == 'T':
if not check_S(i,j):
cnt+=1
# 모든 선생이 감시가 불가능할 때
if cnt == teacher:
answer = True
return
for i in range(n):
for j in range(n):
if graph[i][j] == 'X':
graph[i][j] = 'O'
count +=1
solution(count)
graph[i][j] = 'X'
count -=1
answer = False
solution(0)
if answer:
print('YES')
else:
print('NO')
'지난 글 모음' 카테고리의 다른 글
[week01] 정글 1주일 차 회고 (1) | 2022.04.04 |
---|---|
sw정글 - [week01] 특별한 과제(에세이) (3) | 2022.04.02 |
[백준 python] 18405번 경쟁적 전염 - DFS/BFS (0) | 2022.03.12 |
[백준 python] 18352번 특정 거리의 도시 찾기- DFS/BFS (0) | 2022.03.11 |
[백준 python] 12904번 A와 B 그리디 (0) | 2022.03.11 |