📌 이번에 푼 문제

1. 방문 길이

• 출처 : 프로그래머스 (Summer/Winter Coding(~2018))
• 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49994

잘못된 접근

• 문제 이해를 잘못했다. → "몇 번 움직였냐(이동 횟수)"로 풀었다.

몰랐던 점 / 틀린 이유

1) 간선을 집합에 저장해 서로 다른 선분의 개수를 세야 한다.

구해야 하는 건 이동 횟수가 아니라 처음 걸어본 길(서로 다른 선분)의 개수다.

• 간선 : tuple(sorted([(x, y), (nx, ny)]))
• 집합 : visited = set()
• ⚠️ 선분은 양방향이 같은 길 → sorted로 정렬해 튜플로 만들면 (A→B), (B→A)가 같은 키가 된다.

2) 경계 체크 조건

• ⚠️ 현재 위치를 조건으로 거는 게 아니라(X), 다음 위치가 범위 안일 때(O) 이동한다.
• 좌표 정리 : x, y 시작점 / dx, dy 이동량 / nx, ny 다음점
• 다음점 nx, ny가 범위 안에 있어야 이동(그리고 선분 기록)까지 가능하다.

개선한 풀이

def solution(dirs):
    moves = {'U': (0, 1), 'D': (0, -1), 'R': (1, 0), 'L': (-1, 0)}
    x, y = 0, 0
    visited = set()

    for d in dirs:
        dx, dy = moves[d]
        nx, ny = x + dx, y + dy

        # 다음 위치가 범위 안일 때만 이동
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            # 선분(간선)을 정렬된 튜플로 저장 → 양방향 같은 길로 취급
            visited.add(tuple(sorted([(x, y), (nx, ny)])))
            x, y = nx, ny  # 이동

    return len(visited)

2. 가장 먼 노드

• 출처 : 프로그래머스 (그래프)
• 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49189

핵심

• 양방향 : graph에 두 번 append (a→b, b→a)
• 최단거리 : BFS
  • deque 사용
  • 방문 처리 + 조건 만족 시 큐에 추가
  • 큐에서 꺼내기

풀이

from collections import deque

def solution(n, edge):
    answer = 0
    # 1번 노드에서 가장 멀리 떨어진 노드 개수.
    # 최단경로로 이동했을 때의 간선 개수가 많은 노드

    # 1) 인덱스를 노드 번호로 쓰는 리스트를 만들자.
    ## 빈 이중 리스트를 만든다.
    vertex = [[] for _ in range(n + 1)]
    ## for문을 돌면서 양방향으로 채운다.
    for a, b in edge:
        vertex[a].append(b)
        vertex[b].append(a)

    # 2) visited 만들기 (거리만 구하면 되니까 -1로 미방문 표시만)
    dist = [-1] * (n + 1)
    dist[1] = 0          # 출발점
    q = deque([1])       # 시작 노드 1번을 큐에 넣고 BFS 시작

    while q:
        node = q.popleft()            # 노드 꺼내기
        for nxt in vertex[node]:      # 이웃 보기
            if dist[nxt] == -1:       ## 안 가본 이웃만
                dist[nxt] = dist[node] + 1   ## 거리 적고 큐에 넣기
                q.append(nxt)

    max_dist = max(dist)
    answer = dist.count(max_dist)     # 가장 먼 거리를 가진 노드 개수
    return answer