입력에서 인접 리스트 만들기
대회 문제에서 요구하는 그래프를 만듭니다
입력에서 인접 리스트 만들기은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
그래프란 실제로 무엇인가요
그래프는 노드라고 부르는 점들을 간선이라고 부르는 선으로 연결한 것입니다. 도로로 연결된 도시가 익숙한 그래프의 예입니다. 🗺️
노드와 간선
각 노드는 하나의 대상을 나타내고, 각 간선은 두 노드가 연결되어 있음을 나타냅니다. 대회 문제의 그래프에서는 보통 노드 번호를 1부터 n까지 매깁니다.
인접 리스트
대회 문제에서 가장 많이 사용하는 저장 방식은 인접 리스트입니다. 각 노드에 대해 바로 연결된 이웃 노드의 목록을 저장합니다.
adj = [[] for _ in range(n + 1)]행렬을 사용하지 않는 이유
행렬은 n의 제곱에 해당하는 메모리를 사용하므로 n이 커지면 메모리가 폭발적으로 증가합니다. 인접 리스트는 실제로 존재하는 간선만 저장하므로 규모가 커져도 효율적입니다.
첫 번째 줄 읽기
대부분의 입력은 두 숫자로 시작합니다. n은 노드 수이고 m은 간선 수입니다. 앞으로 읽을 간선의 수를 알 수 있도록 먼저 읽으세요.
n, m = map(int, input().split())한 줄에 간선 하나
다음 m개의 줄에는 각각 u v라는 한 쌍이 주어집니다. 이 하나의 간선은 u와 v가 직접 연결되어 있음을 뜻합니다.
u, v = map(int, input().split())무방향은 양쪽을 뜻합니다
무방향 간선이라면 양쪽 방향으로 연결을 추가하세요. u에서 v로도, v에서 u로도 이동할 수 있습니다.
adj[u].append(v)
adj[v].append(u)방향은 한쪽을 뜻합니다
방향 간선이라면 u에서 v로 가는 연결만 저장합니다. 어떤 종류의 간선인지 알 수 있도록 문제 설명을 주의 깊게 읽으세요.
adj[u].append(v)반복문으로 만들기
m번 반복하면서 각 쌍을 읽고 목록을 채우세요. 반복문이 끝나면 인접 리스트에 그래프 전체가 저장됩니다.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)1부터 시작하는 인덱스와 0부터 시작하는 인덱스
노드가 1부터 시작한다면 n번 인덱스가 유효하도록 목록 크기를 n + 1로 설정하세요. 인덱싱을 혼동하면 눈치채기 어려운 오류가 발생합니다.
노드의 이웃 방문하기
한번 만들고 나면 탐색은 쉽습니다. 노드의 adj를 순회하면 모든 이웃 노드에 한 단계로 도달할 수 있습니다.
for nb in adj[u]:
print(nb)빠른 확인
무방향 간선 u v를 읽었습니다. 무엇을 저장해야 할까요?
복습
이제 인접 리스트로 그래프를 만들 수 있습니다. n과 m을 읽고, 간선을 반복해서 읽으며, 무방향인 경우 양쪽 방향을 모두 추가하세요. 🎉
자주 묻는 질문
“입력에서 인접 리스트 만들기” 강의는 무료인가요?
네 — “입력에서 인접 리스트 만들기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“입력에서 인접 리스트 만들기”에서 뭘 배우나요?
대회 문제에서 요구하는 그래프를 만듭니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“입력에서 인접 리스트 만들기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 입력에서 인접 리스트 만들기
- 가중치 없는 최단 경로를 위한 BFS
- DFS, 재귀와 반복 스택
- 연결 요소와 플러드 필