삼성 SW역량테스트 기출 / 2018 하반기 오후 2번 문제 전투로봇 - BFS / Python 파이썬

 

*문제 출처는 삼성전자, 코드트리에 있습니다.

 

삼멘.. 자소서 제출완

문제 제목: 전투로봇

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/fighting-robot/submissions?page=1&pageSize=20&tags=BFS

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

---

몬스터의 좌표를 구해준 뒤, 문제의 조건대로 구현하면 쉽게 풀린다.

 

자신의 위치에서 가장 위. 가장 왼쪽에 있는 몬스터 좌표 구하는 코드 구할때 람다식을 써줬다.

tmp_list.sort(key = lambda x:(x[2],x[0]-current_point[0],x[1]-current_point[1]))

우선순위가 거리가 짧은게 가장 우선이고, 만약 거리가 같다면 가장 위에 있는것, 그 좌표또한 같다면 가장 왼쪽에 있는 것 순서로 정렬

 

current point 로 뺴주고 정렬한 이유는 만약 현재 좌표가 (2,3) 일떄

내 위에 있는 좌표가 (1,2)와 (1,4)가 있다고 하자.

(1 - 2), (2 - 3) => (-1,-1)  # 나보다 위에 있고, 가장 왼쪽에 있음

(1 - 2), (4 - 3) => (-1,1) # 나보다 위에있지만 위의 좌표보단 오른쪽에 잇음

음수가 나오면 나보다 위쪽, 혹은 왼쪽에 있음을 알 수 있음

 

나의 풀이 - 처음 풀이 (메모리 초과)

이유

visited 를 for문으로 만듦 (사실 이전에 큐에 넣을때 level으로 비교하는 구문있었는데, 오류떠서 이렇게 했더니... 틀림)

 

그래서 고쳐주고 최종 풀이

from collections import deque

n = int(input())

maps = [list(map(int,input().split())) for _ in range(n)]
level = 2
monsters = []
for i in range(n):
    for j in range(n):
        if maps[i][j] == 9:
            current_point = [i,j]
            maps[i][j] = 0
        elif 0 < maps[i][j] and maps[i][j] <= 6:
            monsters.append([i,j])


def bfs(points,start):
    queue = deque([[start[0],start[1],0]])
    visited = [[False] * n for _ in range(n)]
    visited[start[0]][start[1]] = True
    while queue:
        q = queue.popleft()
        qx, qy , distance = q[0],q[1],q[2]
        direct = ((1,0),(-1,0),(0,1),(0,-1))
        if [qx, qy] == [points[0], points[1]]:
            return distance

        for i in range(4):
            x = qx + direct[i][0]
            y = qy + direct[i][1]
            if 0 <= x < n and 0 <= y < n and visited[x][y] == False and maps[x][y] <= level:
                queue.append([x,y,distance + 1])
                visited[x][y] = True

    return -1

kills = 0
answer = 0
while monsters:
    tmp_list = []
    for i,j in monsters:
        if maps[i][j] < level:
            dist = bfs([i,j],current_point)
            if dist != -1:
                tmp_list.append([i,j,dist])
    if not tmp_list:
        break
    tmp_list.sort(key = lambda x:(x[2],x[0]-current_point[0],x[1]-current_point[1]))
    mx,my,mdist = tmp_list[0][0],tmp_list[0][1],tmp_list[0][2]
    current_point = [mx,my]
    maps[mx][my] = 0
    kills += 1
    if kills % level == 0:
        level += 1
        kills = 0
    answer += mdist
    # monsters = [[i,j] for i,j in monsters if [i,j] != [mx,my]]
    monsters.pop(monsters.index([mx,my])) 
print(answer)

 

근데도 시간이  이상해서 보니 min거리를 찾으면 그만 두는 코드부분이 구현이 안돼있었다.

 

아래 코드는 접근을 아예 다르게 했다.

몬스터들의 좌표를 구해서 매번 돌면서 현재 위치에서 각각의 몬스터의 거리를 구하고 업데이트 하는 방식이면,

 

아래 코드는 지금 거리에서 이동했을때 해당 좌표가 만약 나보다 작은 레벨이라면 먹을 수 있는 몬스터로, potential_targets 에 넣고 min_distance 를 업데이트함

from collections import deque

n = int(input())

maps = [list(map(int,input().split())) for _ in range(n)]
level = 2
monsters = []
for i in range(n):
    for j in range(n):
        if maps[i][j] == 9:
            current_point = [i,j]
            maps[i][j] = 0
        elif 0 < maps[i][j] and maps[i][j] <= 6:
            monsters.append([i,j])

# 몬스터와의 거리 계산을 한 번의 BFS에서 처리
def bfs(start):
    queue = deque([[start[0], start[1], 0]])
    visited = [[False] * n for _ in range(n)]
    visited[start[0]][start[1]] = True
    potential_targets = []  # 먹을 수 있는 몬스터 저장
    min_distance = float('inf')  # 최소 거리 저장

    while queue:
        qx, qy, distance = queue.popleft()

        # 가장 가까운 거리를 찾았으면 더 이상 먼 거리는 탐색하지 않음
        if distance > min_distance:
            break

        direct = ((1,0),(-1,0),(0,1),(0,-1))
        for dx, dy in direct:
            x, y = qx + dx, qy + dy
            if 0 <= x < n and 0 <= y < n and not visited[x][y]:
                if maps[x][y] <= level:
                    visited[x][y] = True
                    if 0 < maps[x][y] < level and distance <= min_distance:  # 먹을 수 있는 몬스터
                        potential_targets.append([x, y, distance + 1])
                        min_distance = distance + 1
                    queue.append([x, y, distance + 1])

    if potential_targets:
        # 여러 타겟 중 최적의 타겟을 거리, x, y 순으로 정렬
        potential_targets.sort(key=lambda x: (x[2], x[0], x[1]))
        return potential_targets[0]  # 가장 가까운 타겟 반환

    return None  # 먹을 수 있는 몬스터가 없을 때

kills = 0
answer = 0

while True:
    target = bfs(current_point)
    if target is None:  # 더 이상 먹을 수 있는 몬스터가 없으면 종료
        break

    mx, my, mdist = target
    current_point = [mx, my]
    maps[mx][my] = 0  # 몬스터를 먹음
    kills += 1
    if kills == level:  # 몬스터를 레벨만큼 먹으면 레벨업
        level += 1
        kills = 0
    answer += mdist

print(answer)

속도차이 굳

---

※ 알아야 할 것

- min 설정을 둬보자.. 더 최적화 할 수 있으면 최대한 최적화하자