https://www.acmicpc.net/problem/18428
18428번: 감시 피하기
NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 BFS로 해결하기보다는 문제의 조건을 따라서 해결하면 더 쉬웠던 문제입니다. 처음에 그래프입력을 받으면서 x인 곳을 blank라는 리스트에 따로 추가하고 T인 곳을 teacher이라는 리스트에 따로 추가를 해줍니다. 선생님들은 상, 하 , 좌, 우 4곳으로 볼 수 있고 방해물이 없다면 그래프의 끝까지 조회할 수 있으므로 방향 리스트인 dx, dy를 만들고 bfs함수를 정의합니다. 각 방향을 끝까지 조회하면서 빈칸인 경우 T로 방문처리를 해주거나, 방해물이 있는경우 그 뒤쪽은 볼수 없는 경우를 처리해주고, 학생을 찾은 경우 바로 bfs함수에서 False를 return해주면 쉽게 해결할 수 있습니다. 학생을 찾지 못한 경우는 True를 return해주면 되겠습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
from collections import deque
from itertools import combinations
import copy
n = int(input())
graph = []
teacher = []
blank = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
graph.append(list(input().split()))
for j in range(n):
if graph[i][j] == 'T':
teacher.append((i, j))
elif graph[i][j] == "X":
blank.append((i, j))
def bfs(): # 학생 찾으면 False 반환
q = deque(teacher)
test_graph = copy.deepcopy(graph)
while q:
x, y = q.popleft()
for i in range(4):
temp_x, temp_y = x, y
while True:
nx = temp_x + dx[i]
ny = temp_y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
if test_graph[nx][ny] == 'X':
test_graph[nx][ny] = 'T'
elif test_graph[nx][ny] == 'S':
return False
elif test_graph[nx][ny] == 'O':
break
temp_x, temp_y = nx, ny
else:
break
return True
check = False
for data in list(combinations(blank, 3)):
for x, y in data:
graph[x][y] = 'O'
if bfs():
check = True
break
for x, y in data:
graph[x][y] = 'X'
if check:
print("YES")
else:
print("NO")
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 16234: 국영수(Python) (0) | 2020.12.09 |
|---|---|
| 백준 알고리즘 16234: 인구이동(Python) (0) | 2020.12.07 |
| 백준 알고리즘 14888: 연산자 끼워 넣기(Python) (0) | 2020.12.05 |
| 백준 알고리즘 18405: 경쟁적 전염(Python) (0) | 2020.12.05 |
| 백준 알고리즘 14502: 연구소(Python) (0) | 2020.12.05 |