2021 하계 모각코 3주차

• 오늘의 계획
  • 실리콘밸리 인턴쉽 리액트 작업하기
    • 프로그래머스/백준 사이트에서 알고리즘 문제 풀이(그래프)

---

• 오늘의 회고

  • react 작업
    • 오늘 완료하지 못한 login 작업을 하였다.

  • 그래프 문제 풀이 : 가장 먼 노드(프로그래머스 LEVEL 3)

    • 해결 방법 : 처음에 보자마자 다익스트라를 사용하면 되겠다 싶었는데 더 간단하게 구현할 수 있을 것 같아 방향을 바꿨다.
    • graph에 edge 속 간선을 양방향으로 이어주고, 시작 노드로부터 거리가 1인 노드를 q에 추가하였다.
    • 그 후 q가 비어 있지 않은 동안 반복하며 next 노드까지의 거리(length)가 INF로 초기화된 distance 보다 더 짧다면 갱신 후 그 다음 노드들을 q에 append하는 방식을 통해 문제를 해결하였다.
    • 이 때 distance 배열의 0번째 인덱스에는 INF 값이 들어 있으므로 while문을 돌며 갱신한 maxDistance의 개수를 세는 방식을 활용해 최대 거리 노드의 개수를 구하였다.

  • 코드 :

      ```python
      from collections import deque
      INF = int(1e9)
    
      def solution(n, edge):
          answer = 0
          maxDistance = 0
          graph = [[] for i in range(n+1)]
          distance = [INF] * (n + 1)
          distance[1] = 0
    
          # 간선 이어주기
          for i in edge:
              f, t = i
              graph[f].append(t)
              graph[t].append(f)
    
          q = deque()
    
          # 시작 노드로부터 거리가 1인 노드를 큐에 추가
          for i in graph[1]:
              q.append([i, 1])
    
          while q:
              # next 노드까지의 거리가 length
              next, length = q.popleft()
              # 다음 노드까지의 거리가 더 짧다면 갱신 후 q에 append
              if distance[next] > length:
                  maxDistance = max(maxDistance, length)
                  distance[next] = length
                  for n in graph[next]:
                      q.append([n, length + 1])
    
          # 1번 노드로부터 최대 거리인 노드들의 개수
          answer = distance.count(maxDistance)
    
          return answer
      ```