링크

경주로 건설

난이도

  • 프로그래머스 난이도 3
    • 이게왜 난이도 3
      • 아니 이게 왜 시간초과야! 하는 문제
      • 7점이나 하는 엄청난 문제
    • 시간계산 잘하는 사람이면 잘 풀었을듯
    • 문제푸는 방식은 같은데 좀더 효율적으로 만드느냐가 중점

문제요약

  • 그래프의 가중치를 전부 0으로 만드는 최소 교환 횟수
    • 가중치는 연결된 다른 정점으로 갈때 가지고있는 가중치가 -되고 반대쪽은 +되는 방식으로 교환

접근

    1. 끝 정점일때 연결된 다른 정점에게 가중치 넘기는것을 반복(시간초과)
      • 끝인것을 확인하기위해 정점리스트의 갯수가 1인것을 확인하는 방식을 사용
      • 확인하는 과정 자체가 오래걸리게됨
    1. dfs를 이용
      • dfs의 특징인 끝 노드를 전부 탐색하는 것을 활용

간단 알고리즘

  • 인접리스트 생성
    • adj[0]=[1,2,3] # 정점0과 이어진 정점은 1,2,3이다
  • dfs를 진행
    • a는 정점의 가중치, graph는 인접리스트, visited는 정점방문여부(a와 같은크기),cur은 현재 정점, answer은 정답계산용
    • 핵심
      • 현재 정점에서 방문하지않은 모든 자식의 가중치값 + 자신의 가중치값을 더해준것을 result라고한다.
      • 받아온 answer에는 절대값result를 더해준다.
      • [result, answer]로 반환해준다.
        • 복잡하면 answer은 global로 해서 편하게 계산해도됨
  • 가능여부 계산
    • 모든 정점의 가중치를 더했을때 0이 안되면 불가능

후기

  • 총 3일에 걸쳐 진행한 초 대규모 프로젝트
    • 블록버스터 수준이었다.
  • 내가만든알고리즘(접근 1번째)는 정답은 외치지만 어느순간 안드로메다인 저멀리서 소리도 안들리는 곳까지 계산을 하기위해 대장정을 떠나서 열심히 최적화를 진행
  • 최적화를 해도 해도 시간초과. 계산하는 부분이 핵심인데 이게 시간초과의 핵심이기도 해서 과감히 버리게됨
  • 검색중 월간 코드챌린지 해설(무려공식)이 있다고 해서 실수인것처럼 한번 확인함
  • dfs를 쓰면된다고 하고 greedy까지 태그되어있어서 햇갈렸는데 그냥 dfs로 생각하면 편함
  • dfs도 잘못 만들어서 시간초과가 나옴
    • sys.setrecursionlimit(300000)를 잊지 맙시다.