스미스요원

문제 설명

풀이 방법

• 접근 방식

    ◦  특별한 수학적 규칙이 존재하지 않는다. 노드를 돌면서 양의 수가 최대가 되는 경우를 찾는 탐색 문제이다.

• 핵심 아이디어

    ◦  문제에서 제시된 트리의 형태는 이진 트리이나, 매 분기마다 방문 가능한 노드는 자식 노드 단 두개가 아닌 현재 방문한 노드의 모든

         자식 노드라는 점이 포인트

          -  즉 방문한 노드와 방문하지 않은 노드를 관리하기 위한 배열이 필요하다.

    ◦  이를 단순하게 생각해서, 존재하는 모든 노드 관계를 훑으면서 부모는 방문했는데 자식은 방문을 안했다면 바로 방문하는 식으로

         파고 들어가는 DFS 로직을 작성하면 된다.

    ◦  늑대의 수가 양보다 더 많아지면 그 이후로 양의 수는 양수가 될 수 없으므로, 더이상 DFS 트리를 파고들어 갈 필요가 없다.

         바로 재귀를 종료해주자.

• 알고리즘

    ◦  DFS 트리

          -  단 탐색 트리의 형태(각 노드의 자식의 개수)가 일정하지는 않다.

파이썬 코드

def solution(info, edges):
    # 방문한 노드를 기록하는 리스트
    visited = [0] * len(info)
    visited[0] = 1
    answer = []
    
    def dfs(sheep, wolf, visited):
        # 양과 늑대의 수에 따른 상태 집계
        if(sheep > wolf):
            answer.append(sheep)
        else:
            return
        
        # 방문할 노드가 남아있는 경우
        for i in edges:
            if(visited[i[0]] == 1 and visited[i[1]] == 0):
                newVisited = visited.copy()
                newVisited[i[1]] = 1
                
                # 새로 방문한 노드의 양/늑대 집계
                if(info[i[1]] == 1):
                    dfs(sheep, wolf+1, newVisited)
                else:
                    dfs(sheep+1, wolf, newVisited)
                
    # return answer
    dfs(1,0,visited)
    return max(answer)

문제 설명

풀이 방법

• 접근 방식

    ◦  그래프 최단거리로 접근하는 문제이다.

    ◦  먼저 그래프상의 노드간의 최단거리를 계산해 문제를 간단하게 구조화 한 다음 필요한 처리를 추가해주자.

• 핵심 아이디어

    ◦  무지와 어피치가 헤어지는 지점을 어디로 했을 때 택시요금이 최저가 되는지를 찾으면 된다.

    ◦  즉 (시작점 ~ 헤어지는 지점) + (헤어진 지점 ~ 무지의 집) + (헤어진 지점 ~ 어피치의 집) 이 최저가 되는 헤어지는 지점을 찾는 문제

• 알고리즘

    ◦  floyd warshall 알고리즘을 사용해 먼저 노드간의 최단거리 연산을 해주었다.

    ◦  그 다음 모든 노드에 대해 해당 노드가 헤어지는 지점일 때의 택시 요금을 비교하여 최저가 되는 상황의 요금을 구했다.

파이썬 코드

def solution(n, s, a, b, fares):
    # set variables
    INF = int(1e9)
    graph = [[INF] * (n) for i in range(n)]
    
    # initialize
    for i in range(0,n):
        graph[i][i] = 0
    
    # 간선 정보 입력
    for i in fares:
        graph[i[0]-1][i[1]-1] = i[2]
        graph[i[1]-1][i[0]-1] = i[2]
    
    # floyd warshall 알고리즘
    for i in range(n):
        for j in range(n):
            for k in range(n):
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
    
    # 최단거리 탐색
    minPath = INF
    for i in range(n):
        minPath = min(minPath, graph[s-1][i] + graph[i][a-1] + graph[i][b-1])
    return minPath

문제 설명

풀이 방법

• 접근 방식

    ◦  라이언이 어피치를 가장 큰 점수로 차이로 어피치를 이길 수 있는 경우를 구해야 하는 문제이다.

          -  점수차이가 나는데 특별한 수학적 규칙이 없고, 라이언이 화살을 어떻게 쏘는가 그 결과에 달려있다.

          -  화살을 쏠 수 있는 모든 경우의 수를 구하고, 그 결과를 비교해 점수차의 최댓값을 구하는 문제이다.

    ◦  보통 여러가지 경우의 수에 대한 결과를 비교할 땐 BFS를 사용하는게 편하다. 이 문제도 마찬가지!

• 핵심 아이디어

    ◦  10점 ~ 0점 과녁을 순회하면서, 각 점수 과녁에서 라이언이 할 수 있는 선택은 2가지이다.

          -  화살을 쏘지 않고 아껴둔다. (사용한 화살 : 0개)

          -  어피치가 쏜 화살보다 1개 더 쏜다. (사용한 화살 : 어피치가 쏜 화살 +1개)

    ◦  과녁은 10점 ~ 0점 총 11개 이고, 선택은 2가지 이니까 총 2의 11제곱에 대한 경우의 수를 자식 노드가 2개인 이진트리로 집계한 후
         결과를 비교하면 된다.

• 알고리즘

    ◦  이진트리 BFS

          -  각 점수 과녁을 순회하면서 화살을 쏘거나, 쏘지 않거나로 자식 노드를 확장해 나간다.

          -  노드 확장 종료 조건 = 화살을 다 쐈음 or (10점~0점 과녁 순으로 순회할 때)현재 과녁이 마지막 과녁임

              -  현재 과녁이 마지막 과녁인 경우, 남은 화살을 전부 쏜다.

              -  또한 어피치보다 무조건 1개 더 쏘는 상황이 반복되다보면 라이언이 쏠 수 있는 화살 개수보다 더 쏘게되는 상황이
                  발생할 수 있다. 이는 경기상에서 고려하지 않는 상황이므로, 이 케이스는 무시하는 로직을 추가해 줘야 한다.

          -  노드 확장이 종료되면 그 케이스의 라이언과 어피치의 점수 차이를 구한다.

          -  모든 경우의 수를 돌면서, 점수 차이가 최대가 되는 값을 계속 업데이트한다.

파이썬 코드

def solution(n, info):
    # set variables
    bfs = [(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])]
    maxScore = 0
    answer = []
    
    while(bfs):
        # 현재 쏘려는 점수, 과녁 현황
        idx, arrowList = bfs.pop(0)
        
        # 종료 조건1 : 화살을 모두 쏜 경우
        if(sum(arrowList) == n):
            apeach, lion = 0, 0
            # 점수 차이 집계
            for i in range(11):
                if(arrowList[i]+info[i] == 0):
                    continue
                if(arrowList[i] <= info[i]):
                    apeach += 10 - i
                else:
                    lion += 10 - i
            # 라이언이 이긴 경우 : 점수 차이 최댓값 업데이트
            if apeach < lion:
                if maxScore > (lion - apeach):
                    continue
                if maxScore <= (lion - apeach):
                    maxScore = lion - apeach
                    answer = arrowList.copy()
            
        # 종료 조건2 : 화살을 오버해서 쏜 경우 (무시)
        elif(sum(arrowList) > n):
            continue
        
        # 종료 조건3 :  마지막 과녁인데 화살이 남은 경우 (남은 화살을 다 쏜다)
        elif(idx == 10):
            arrowList[10] = n - sum(arrowList)
            bfs.append((-1,arrowList))
        
        # 경기 진행중
        else:
            # 어피치보다 1발 더 쏘기
            temp = arrowList.copy()
            temp[idx] = info[idx]+1 
            bfs.append((idx+1, temp))
            
            # 쏘지 않기
            temp = arrowList.copy()
            temp[idx] = 0 
            bfs.append((idx+1, temp))
    
    # return answer
    if(not answer):
        return [-1]
    return answer