문제
비행기에서 뛰어내려 특정 좌표에 도착해 전투를 시작한다. 전투 투시경을 통해 현재 위치에서 모든 적의 위치가 보인다. 일단 전투를 시작하기 전 현재 위치에서 각각의 적의 위치까지 도착하는데에 걸리는 시간을 미리 구해놓을려고 한다. 거리는 현재 위치 (a, b)와 적의 위치 (c, d)를 알면 |a-c| + |b-d| 로 구할 수 있다. 이동하는데에 소요되는 시간은 격자판 기준 1칸 이동시 1분이 소요된다.
이동은 상하좌우로만 할 수 있으며, 대각선으로는 이동할 수 없다. 또한, 자신의 레벨보다 높은 레벨의 적을 뚫고 지나갈 수 없다. 자신의 레벨과 같은 레벨의 적은 잡을 수는 없으나, 지나갈 수 있다. 만약 거리가 같은 적이 2명 이상일 경우 y 좌표가 작은 적에게 우선 이동한다. 거리가 같고, y 좌표가 동일한 적이 2명 이상일 경우 x 좌표가 작은 적을 향해 이동한다.
전장의 정보와 낙하 지점이 주어졌을때, 낙하 지점에서 각 적까지의 시간을 구하여 출력해보자.
입력
첫 번째 줄에 전장의 크기 N, 현재 레벨 K가 주어진다.
두 번째 줄부터 N개의 줄에 걸쳐 전장의 정보가 주어진다. 각 줄은 N개의 숫자로 이루어져 있으며, 각 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중에 하나이다. 0은 아무것도 없음, 1 ~ 8은 적, 9는 낙하 지점을 의미한다. 9는 하나만 주어진다.
왼쪽 최상단의 좌표는 (1, 1)이다.
(2 ≤ N ≤ 20, 2 ≤ K ≤ 9)
출력
주어진 전장의 정보에서 현재 레벨보다 낮은 적의 위치 칸은 낙하 지점에서의 시간을 출력한다. 낙하 지점에서 출발하여 도착할 수 없는 칸은 '-1'을 출력한다. 같은 레벨일 경우 '.'을 출력하고, 높은 레벨일 경우 'X'를 출력한다. 낙하 지점은 '*'로 출력한다. 나머지 칸의 경우 '0'을 출력한다.
입력의 예 1
5 2
0 1 0 1 0
0 0 0 0 2
0 2 0 2 0
3 3 9 0 0
1 3 0 0 0출력의 예 1
0 4 0 4 0
0 0 0 0 .
0 . 0 . 0
X X * 0 0
-1 X 0 0 0입력의 예 2
6 4
3 2 5 0 9 0
0 3 0 0 4 0
2 0 0 2 5 4
7 0 0 1 3 2
2 2 0 1 7 1
4 3 2 3 8 2 출력의 예 2
6 5 X 0 * 0
0 4 0 0 . 0
6 0 0 3 X .
X 0 0 4 5 4
8 7 0 5 X 5
. 8 7 6 X 6
틀린 풀이
- 결과값을 저장할 맵을 -1로 초기화(갈수 없는 곳) 생성
- 결과값 출력
-> 같은 레벨일 경우 '.'을 출력
->높은 레벨일 경우 'X'를 출력
-> 낙하 지점은 '*'로 출력한다.
-> 원래 0이였던 칸은 '0'을 출력한다.
- 위쪽, 오른쪽, 아래, 왼쪽을 BFS로 돌아다니는데, 공격수의 레벨보다 큰 경우에는 돌지 않는다.
- 그러면 -1을 지킬 수 있을거라고 생각했음
- 인접한 작은 애들이 돌아줄 것이라고 생각했음
- 1번 테스트 케이스는 맞게 나오는데 2번부터는 틀리게 나온다
from collections import deque
def level_check_cal(row, level_data, attacker_x, attacker_y) :
result_list = [[-1] * row for _ in range(row)]
print(result_list)
for x in range(row) :
for y in range(row) :
if level_data[x][y] == 0 : #원래 값이 0인 값은 그냥 0임
result_list[x][y] = 0
else :
now_enemy = abs(attacker_x - x) + abs(attacker_y - y)
if now_enemy == 0 : #|공격수x-현재값x|+|공격수y-현재값y| = 0 이면 공격수 자리이므로 * 표시
result_list[x][y] = "*"
continue
print(result_list)
def level_check_move_BFS(row, level_data, start_x, start_y, attacker_level) :
result_list = [[-1] * row for _ in range(row)]
visite_list = [[0] * row for _ in range(row)]
print(visite_list)
dx = [-1, 0, 1, 0] #위 0, 오른 1, 아래쪽 2, 왼쪽 3
dy = [0, 1, 0, -1]
dq = deque() #BFS를 위한 큐 생성
dq.append((start_x, start_y)) #1. 큐에 시작점 추가
visite_list[start_x][start_y] = True #2. 큐에 넣은 시작점은 방문처리
result_list[start_x][start_y] = "*"
#위 오른쪽 아래 왼쪽 움직이는 BFS 시작
while dq : #3. 큐가 텅 빌때까지 방문
now_idx = dq.popleft() #큐에는 [(x, y)] 좌표 들어감
for i in range(4) : #위 0, 오른 1, 아래쪽 2, 왼쪽 3 방향 반복하면서 큐에 4방향 순회
next_x = now_idx[0] + dx[i] #큐에 들어간 좌표 중 다음 x좌표[0]
next_y = now_idx[1] + dy[i] #큐에 들어간 좌표 중 다음 y좌표[1]
if 0 <= next_x <= (row-1) and 0 <= next_y <= (row-1) and visite_list[next_x][next_y] is not True: #테두리 이상 벗어나지 않는 조건, 이미 방문한 곳은 재방문 하지않음
if level_data[next_x][next_y] <= attacker_level : #attacker_level의 레벨보다 큰 값은 큐에 넣지 않음
visite_list[next_x][next_y] = True #방문한 곳은 재방문 방지를 위해 visite_list를 True 처리
dq.append((next_x, next_y))
if level_data[next_x][next_y] != 0 and level_data[next_x][next_y] < attacker_level : #현재 레벨보다 낮은 적의 위치 칸은 낙하 지점에서의 시간 출력
result_list[next_x][next_y] = abs(attacker_x - next_x) + abs(attacker_y - next_y) #거리 |공격수x-현재값x|+|공격수y-현재값y|
if level_data[next_x][next_y] == 0 : #원래 0이던 자리는 0
result_list[next_x][next_y] = "0"
if level_data[next_x][next_y] == attacker_level : #같은 레벨인 경우 .
result_list[next_x][next_y] = "."
elif attacker_level < level_data[next_x][next_y] : #높은 레벨인 경우 x
result_list[next_x][next_y] = "X"
print("result_list :")
print(result_list)
return result_list
if __name__ == "__main__":
row, attacker_level = map(int, input().split()) #n*n 행렬 너비, 레벨 입력
level_data = []
result_data = []
attacker_x = -1 #공격수 x좌표, y좌표 초기 값은 -1
attacker_y = -1
for i in range(row) : #맵 데이터 입력 받아서 맵 생성
level_data.append(list(map(int, input().split())))
print("level_data")
print(level_data)
for x in range(row) :
for y in range(row) :
if level_data[x][y] == 9 : #9(공격수 좌표) 찾기
attacker_x = x #공격수 x좌표
attacker_y = y #공격수 y좌표
print("level_check_move_BFS")
level_check_move_BFS(row, level_data, attacker_x, attacker_y, attacker_level) #공격자의 시작점(attacker_x, attacker_y)으로부터 BFS 시작
풀이2 - 정답
1. 공격수 좌표를 시작점으로 x, y로 움직 일 수 있는지 있는지(True), 없는 곳 체크(Flase)
-> 범위 밖은 안감 0부터 row까지(if 0 <= next_x <= (row-1) and 0 <= next_y <= (row-1) )
-> 이미 방문한 곳은 가지않는다(if visite_list[next_x][next_y] is not True)
-> 방문할 곳이 0이거나 레벨이 작거나 같은 경우 방문 가능(if level_list[next_x][next_y] == 0 or level_list[next_x][next_y] <= attacker_level)
visite_list 결과
[[True, True, True, True, True],
[True, True, True, True, True],
[True, True, True, True, True],
[False, False, True, True, True],
[False, False, True, True, True]]
2. 공격수 좌표를 시작점으로 거리 구하기(BFS 최단거리)(distance_list[next_x][next_y] = distance_list[now_idx[0]][now_idx[1]] + 1 )
-> BFS를 이용해서 기존 거리 + 1이 다음 방문할 거리
distance_list 결과
[[5, 4, 3, 4, 5],
[4, 3, 2, 3, 4],
[3, 2, 1, 2, 3],
[0, 0, 0, 1, 2],
[0, 0, 1, 2, 3]]
3. level_list : 레벨 적혀있는 리스트,
visite_list : 방문 가능성 리스트,
distance_list : 거리 적혀있는 리스트를 이용해서 조건 프린트
from collections import deque
#level_list : 레벨 적혀있는 리스트
#visite_list : 방문 가능성 리스트
#distance_list : 거리 적혀있는 리스트
def put_result(row, attacker_level, level_list, visite_list, distance_list, attacker_x, attacker_y) :
result_list = [[0] * row for _ in range(row)]
for x in range(row) :
for y in range(row) :
if level_list[x][y] != 0 and visite_list[x][y] is True : #visite_list로 갈수 있는 곳(True) 체크
if level_list[x][y] == attacker_level : #레벨이 같은 경우 "."
result_list[x][y] = "."
if level_list[x][y] < attacker_level : #작은 경우 거리 출력
result_list[x][y] = distance_list[x][y]
if visite_list[x][y] is False : #visite_list로 갈수 없는 곳(False) 체크
if level_list[x][y] > attacker_level :
result_list[x][y] = "X" #갈수 없는 곳중 레벨보다 큰 경우 "X"
if level_list[x][y] < attacker_level :
result_list[x][y] = "-1"
result_list[attacker_x][attacker_y] = "*" #공격자 좌표는 *
return result_list
#공격수 좌표를 시작점으로 갈수있는 곳, 갈수 없는 곳 체크
#공격수 좌표를 시작점으로 거리 구하기
def do_BFS(row, attacker_level, level_list, attacker_x, attacker_y) :
visite_list = [[False] * row for _ in range(row)]
distance_list = [[0] * row for _ in range(row)]
dx = [-1, 0, 1, 0] #위 0, 오른 1, 아래쪽 2, 왼쪽 3
dy = [0, 1, 0, -1]
dq = deque() #BFS를 위한 큐 생성
dq.append((attacker_x, attacker_y)) #1. 큐에 시작점 추가
visite_list[attacker_x][attacker_y] = True #2. 큐에 넣은 시작점은 방문처리
#위 오른쪽 아래 왼쪽 움직이는 BFS 시작
while dq : #3. 큐가 텅 빌때까지 방문
now_idx = dq.popleft() #큐에는 [(x, y)] 좌표 들어감
for i in range(4) : #위 0, 오른 1, 아래쪽 2, 왼쪽 3 방향 반복하면서 큐에 4방향 순회
next_x = now_idx[0] + dx[i] #큐에 들어간 좌표 중 다음 x좌표[0]
next_y = now_idx[1] + dy[i] #큐에 들어간 좌표 중 다음 y좌표[1]
if 0 <= next_x <= (row-1) and 0 <= next_y <= (row-1) : #테두리 이상 벗어나지 않는 조건
if visite_list[next_x][next_y] is not True: #이미 방문한 곳은 재방문 하지않음
if level_list[next_x][next_y] == 0 or level_list[next_x][next_y] <= attacker_level : #방문할 곳이 0이거나 레벨이 작거나 같은 경우 방문 가능
visite_list[next_x][next_y] = True #방문한 곳은 재방문 방지를 위해 True 처리
dq.append((next_x, next_y))
#distance_list[next_x][next_y] = abs(attacker_x - next_x) + abs(attacker_y - next_y) #틀림 단순 공격자에서 해당 좌표까지 거리
distance_list[next_x][next_y] = distance_list[now_idx[0]][now_idx[1]] + 1 #공격자가 못가는 경우를 피해서 가는 최단 거리
return put_result(row, attacker_level, level_list, visite_list, distance_list, attacker_x, attacker_y)
if __name__ == "__main__":
row, attacker_level = map(int, input().split()) #n*n 행렬 너비, 레벨 입력
data = []
level_data = []
result_data = []
attacker_x = -1 #공격수 x좌표, y좌표 초기 값은 -1
attacker_y = -1
for x in range(row) : #맵 데이터 입력 받아서 맵 생성
data = list(map(int, input().split()))
level_data.append(data)
for y in range(len(data)) : #입력 받으면서 공격수 9 찾기
if data[y] == 9 :
attacker_x = x
attacker_y = y
result = do_BFS(row, attacker_level, level_data, attacker_x, attacker_y)
for i in range(row) :
print(" ".join(map(str, result[i])))
'코테풀이 > BFS' 카테고리의 다른 글
| 전장속으로 - 최종 (0) | 2022.02.15 |
|---|---|
| 전장속으로 - E (0) | 2022.02.14 |
| 전장속으로 - D (0) | 2022.02.14 |
| 전장속으로 - B(두 좌표 거리) (0) | 2022.02.14 |
| 전장속으로 - A (0) | 2022.02.14 |