IP는 신뢰할 수 없는 통신과 비연결형 통신이라는 한계가 있습니다.
전송 계층은 이러한 IP의 한계를 극복하여 신뢰성 있는 통신과 연결형 통신을 제공합니다.

이러한 전송 계층 프로토콜로는 TCP와 UDP가 있습니다.

이번 포스팅에서는 TCP와 UDP의 차이를 알아보고, 연결형 통신 프로토콜인 TCP에서의 연결 수립 과정(3-way Handshake)에 대해 살펴보겠습니다.

2. TCP와 UDP 차이

TCP와 UDP는 모두 전송 계층에서 데이터를 보내기 위한 프로토콜이지만, 성격이 크게 다릅니다.

먼저 TCP는 연결형 통신입니다. 데이터를 보내기 전에 먼저 상대와 연결을 수립하고, 그 연결을 통해 데이터를 전송합니다.
이 과정 덕분에 TCP는 데이터가 순서대로 도착하는지, 손실된 데이터는 없는지를 확인할 수 있으며, 신뢰성을 제공하는 프로토콜이라고 할 수 있습니다.
또한, 너무 빨리 보내서 수신 측이 처리하지 못하면 속도를 조절하는 흐름 제어와, 네트워크가 혼잡할 때 전송 속도를 조절하는 혼잡 제어 기능도 제공합니다.
그래서 웹 브라우징, 이메일, 파일 전송처럼 정확한 데이터 전달이 중요한 서비스에서 주로 사용됩니다.

반면 UDP는 비연결형 통신이며, 신뢰성이 없는 프로토콜입니다. 데이터를 보내기 전에 별도의 연결을 만들지 않고, 바로 데이터를 전송합니다.
이 때문에 UDP는 데이터가 순서대로 도착하는지 확인하지 않으며, 일부 데이터가 손실될 수도 있습니다. 하지만 연결을 만들고 확인하는 과정이 없으므로 TCP보다 속도가 빠르고 오버헤드가 적습니다. 그래서 실시간 스트리밍, 온라인 게임, 화상 통화처럼 속도가 중요하고 일부 데이터 손실이 허용되는 서비스에서 주로 사용됩니다.

3. TCP와 UDP 전송 방식

TCP와 UDP는 데이터 전송 방식에서 큰 차이를 보입니다.

• TCP는 연결형 통신이므로, 데이터를 보내기 전에 먼저 상대와 연결을 수립합니다.
  연결이 수립되면 데이터를 순서대로 전송하며, 손실된 데이터는 재전송하고, 순서를 보장합니다.
  데이터를 모두 주고받은 뒤에는 안전하게 연결을 종료합니다.
  정리하면 TCP의 전송 과정은 다음과 같습니다.

  1. 연결 수립 (3-Way Handshake)
  2. 데이터 전송
  3. 연결 종료 (4-Way Handshake)

• UDP는 비연결형 통신이므로, 데이터를 보내기 위해 연결을 만들 필요가 없습니다.
  데이터를 연결 없이 보내며, 순서나 손실 여부를 확인하지 않습니다.
  따라서 전송 속도가 빠르고 오버헤드가 적지만, 신뢰성은 보장되지 않습니다.

TCP는 신뢰성과 순서 보장, UDP는 빠른 전송과 낮은 오버헤드가 특징입니다.

4. 3-Way Handshake

3-Way Handshake는 TCP가 통신을 시작할 때 사용하는 연결 수립 과정입니다.
송신 측과 수신 측이 서로 통신할 준비가 되었는지를 확인하고, 양방향으로 동기화(Synchronize)를 수행합니다.

과정은 총 세 단계로 이루어집니다.

1. SYN (Synchronize)

   • 클라이언트가 서버에게 연결 요청(SYN)을 보냅니다.
   • 이때 "내가 보낸 데이터의 순서를 x번부터 시작하겠다"라는 식으로 시퀀스 번호(Sequence Number)를 함께 보냅니다.

2. SYN + ACK (Synchronize + Acknowledge)

   • 서버가 요청을 수락하며 클라이언트에게 다음 기대하는 번호는 x+1번이라고 응답(ACK) 합니다.
   • 동시에 서버 자신의 시퀀스 번호도 설정(SYN)하여 보냅니다.
   • 즉, "좋아! 난 네 요청을 받았고, 내 데이터는 y번부터 시작할게"라는 뜻입니다.

3. ACK (Acknowledge)

   • 클라이언트가 요청을 수락하며 서버에게 다음 기대하는 번호는 y번이라고 응답(ACK) 합니다.
   • 이제 양쪽 모두 통신을 시작할 준비가 완료됩니다.

3번의 메시지 교환을 통해 양측이 연결 의사를 확인하고, 시퀀스 번호를 동기화하여 데이터 전송 준비가 완료됨을 보장하는 과정이 바로 3-Way Handshake입니다. 이를 통해 TCP는 신뢰성 있는 연결을 제공합니다.

5. 4-Way Handshake

4-Way Handshake는 TCP 연결을 종료할 때 사용되는 과정입니다.
통신을 끝내려는 쪽과 이를 확인하는 쪽이 서로 연결을 안전하게 닫기 위해 4번의 메시지를 주고받는 절차입니다.

과정은 총 네 단계로 이루어집니다.

1. FIN (Finish)

   • 클라이언트가 서버에게 연결을 종료하겠다(FIN)는 요청을 보냅니다.
   • 이때 클라이언트는 더 이상 보낼 데이터가 없음을 알립니다.

2. ACK (Acknowledge)

   • 서버가 FIN을 받고, 알겠다(ACK)는 응답을 보냅니다.
   • 하지만 서버는 아직 보낼 데이터가 남아 있을 수도 있으므로 바로 연결을 닫지는 않습니다.

3. FIN (Finish)

   • 서버가 자신도 더 이상 보낼 데이터가 없을 때, 연결 종료 요청(FIN)을 클라이언트에게 보냅니다.

4. ACK (Acknowledge)

   • 클라이언트가 FIN을 받고, 알겠다(ACK)는 응답을 보냅니다.
   • 이제 양측 모두 데이터를 주고받을 필요가 없으므로 연결이 완전히 종료됩니다.

4번의 메시지 교환을 통해 양측이 안전하게 데이터를 모두 전송했음을 보장하고, 연결을 정상적으로 종료하는 과정이 바로 4-Way Handshake입니다.

6. TCP의 신뢰성과 전송 제어

TCP는 데이터를 안정적이고 정확하게 전달하기 위해 여러 가지 기능들을 제공합니다.
주요 기능으로는 재전송을 통한 오류 제어, 순서 보장, 흐름 제어, 혼잡 제어가 있습니다.

1. 재전송을 통한 오류 제어

• 데이터를 보낸 후 ACK를 받지 못하면 타임아웃 재전송을 수행합니다.
• 중복 ACK를 여러 번 받으면 빠른 재전송(Fast Retransmit)으로 즉시 데이터를 다시 보냅니다.
• 이 과정을 통해 손실된 데이터 없이 정확하게 전송할 수 있습니다.

2. 순서 보장

• 패킷이 순서대로 도착하지 않아도 TCP가 순서를 재조립하여 애플리케이션에 올바른 순서로 전달합니다.
• 체크섬을 사용해 데이터 손상 여부를 확인하고, 필요하면 재전송합니다.

3. 흐름 제어 (Sliding Window)

• 수신 측의 처리 능력을 고려하여 송신 속도를 조절합니다.
• 슬라이딩 윈도우 방식을 사용하여, 수신 측이 처리 가능한 데이터 양(윈도우 크기)을 송신 측에 알려주고,
  송신 측은 해당 범위 내에서 데이터를 전송하며, ACK를 받으면 창(Window)을 앞으로 이동시켜 다음 데이터를 보냅니다.

4. 혼잡 제어

• 네트워크가 혼잡할 때 전송 속도를 조절하여 패킷 손실을 줄이고 효율적으로 데이터를 전달합니다.
• 대표적인 알고리즘으로는 Slow Start, Congestion Avoidance, Fast Retransmit, Fast Recovery 등이 있습니다.

TCP는 이러한 기능 덕분에 데이터 손실 없이 안정적인 통신을 보장합니다.

7. 마무리

이번 포스팅에서는 TCP와 UDP의 차이와, TCP에서 데이터를 안정적으로 전송하기 위한 연결 수립과 종료 과정(3-Way/4-Way Handshake), 그리고 TCP의 전송 제어 기능에 대해 살펴보았습니다.

• TCP는 연결형 통신으로, 신뢰성, 순서 보장, 흐름 제어, 혼잡 제어 기능을 통해 데이터를 안전하게 전달합니다.
• UDP는 비연결형 통신으로, 빠른 전송과 낮은 오버헤드를 제공하지만 신뢰성은 보장되지 않습니다.

이번 포스팅에서 배운 내용을 통해 네트워크 전송 방식 (TCP/UDP)에 대한 개념을 명확히 구분할 수 있을 것입니다.

네트워크를 공부하다 보면 흔히 "IP 주소만 있으면 패킷을 보낼 수 있다"라고 생각하기 쉽습니다.
하지만 현실은 그렇게 간단하지 않습니다.
실제로 패킷이 이더넷을 통해 전달되려면 MAC 주소가 반드시 필요합니다.
이때 IP → MAC 주소 변환을 담당하는 프로토콜이 바로 ARP (Address Resolution Protocol) 입니다.

이번 글에서는 ARP 요청·응답 과정을 중심으로

1. 같은 네트워크 내에서 이더넷 프레임이 호스트 → 스위치 → 라우터로 전달되는 과정

2. 서로 다른 네트워크로 패킷이 이동할 때 라우터를 거치는 과정

을 살펴보겠습니다.

2. 패킷과 이더넷 프레임

패킷과 이더넷 프레임, 뭐가 다른걸까?

네트워크를 이해하려면 "패킷"과 "프레임"의 차이를 먼저 짚어야 합니다.

• 패킷(Packet)

  • 네트워크 계층(L3)에서 다루는 데이터 단위
  • IP 헤더 + 데이터(payload) 로 구성
  • 목적지 IP 주소, 출발지 IP 주소가 들어있음
  • "논리적 주소" → 어디로 가야 할지를 알려줌

• 이더넷 프레임(Ethernet Frame)

  • 데이터 링크 계층(L2)에서 다루는 데이터 단위
  • MAC 헤더 + 패킷 + FCS로 구성
  • 목적지 MAC 주소, 출발지 MAC 주소가 들어있음
  • 실제 케이블이나 무선 매체를 통해 물리적으로 이동하는 단위

쉽게 말해
패킷은 "택배 상자 안에 담긴 내용물", 이더넷 프레임은 "송신지와 목적지의 물리 주소가 적힌 택배 상자"라고 볼 수 있습니다.

3. 패킷은 IP 주소만으로 이동할 수 있을까?

패킷은 목적지 IP 주소만으로 이동할 수 없다.

IP 주소는 논리적인 위치 정보일 뿐입니다. 택배 상자에 목적지가 적혀있지 않다면 이동할 수 없겠죠? 따라서 실제 이더넷 프레임을 전송하려면 목적지 MAC 주소가 필요합니다.

• 호스트 A(192.168.1.10)가 호스트 B(192.168.1.20)에게 패킷을 보내려면,
  먼저 B의 MAC 주소를 알아야 합니다.

• 만약 B의 MAC 주소를 모르면? → ARP 요청이 필요합니다.

4. ARP 요청

호스트가 목적지의 MAC 주소를 알아내기 위해 ARP 요청을 브로드캐스트로 보냅니다. 여기서 브로드캐스트란 "같은 네트워크"에 있는 모든 장비에게 데이터를 전달하는 것을 말합니다.

"IP 주소가 192.168.1.20인 장치 있니? 있다면 네 MAC 주소 좀 알려줘!"

스위치가 호스트로부터 브로드캐스트 프레임을 받으면 이를 모든 포트로 전달합니다. 이 과정에서 스위치는 프레임의 출발지 MAC 주소를 스위치 테이블에 학습합니다.

<스위치 테이블>

5. ARP 응답

목적지 호스트 B는 자신의 IP가 요청에 있는 것을 확인하면 호스트 A로 유니캐스트 ARP 응답을 보냅니다. 여기서 유니캐스트란 특정 단말 1대로 데이터를 전송하는 것을 말합니다.

"나는 192.168.1.20이고, 내 MAC 주소는 BB-BB-BB-BB-BB-BB야!"

스위치는 이 ARP 응답을 받으면서 B의 MAC 주소와 연결된 포트를 학습하여 테이블에 추가합니다.

<스위치 테이블>

호스트가 목적지의 MAC 주소가 적힌 이더넷 프레임을 스위치로 보내면, 스위치는 학습한 스위치 테이블의 정보를 통해 목적지 MAC 주소에 해당하는 포트로 프레임을 전달하는 역할을 합니다.

6. 다른 네트워크로의 이동은 어떻게 하는걸까?

호스트 A(192.168.1.10)가 다른 네트워크(예: 192.168.2.20)의 호스트 B로 데이터를 보내려 한다면, 호스트 A는 B의 MAC 주소를 직접 알 수 없습니다. 이때, 다른 네트워크로 데이터를 전달하는 최적 경로를 결정하는 역할은 라우터가 담당합니다.
따라서 호스트 A는 라우터(기본 게이트웨이)의 MAC 주소를 목적지로 하는 이더넷 프레임에 패킷을 담아 전송합니다.

라우터는 받은 이더넷 프레임 속 패킷을 확인하고, 목적지 IP를 기준으로 다음 네트워크로의 최적 경로를 라우팅 테이블에서 결정합니다.
그 후 라우터는 다음 네트워크의 목적지 MAC 주소를 ARP로 확인하고, 해당 MAC 주소를 이용해 새로운 이더넷 프레임에 패킷을 담아 전송합니다. 이 과정은 패킷이 목적지 네트워크에 도착할 때까지 각 라우터(한 홉)를 거칠 때마다 반복됩니다.
즉, 패킷은 각 네트워크마다 다음 홉 라우터의 MAC 주소를 확인하고 새로운 이더넷 프레임에 담겨 전송되는 과정을 거치면서 목적지에 도달하게 됩니다.

7. 핵심 요약

1. 패킷과 이더넷 프레임 구분

   • 패킷: 논리적 주소(IP) 포함, “택배 상자 안의 내용물”
   • 이더넷 프레임: 물리적 주소(MAC) 포함, “송신지·목적지 표시 택배 상자”

2. 같은 네트워크 내에서의 프레임 전달

   • 목적지 MAC 주소를 모르면 ARP 요청(브로드캐스트)
   • 목적지 호스트가 ARP 응답(유니캐스트)
   • 스위치는 출발지/목적지 MAC 주소를 스위치 테이블에 학습하여 전달

3. 다른 네트워크로의 프레임 전달

   • 호스트는 목적지 MAC을 직접 알 수 없으므로 라우터 MAC으로 프레임 전송
   • 라우터는 패킷의 목적지 IP → 라우팅 테이블 → 다음 홉 결정 → ARP로 다음 홉 MAC 확인 → 새 프레임 전송
   • 각 홉마다 반복하여 패킷이 최종 목적지에 도달

핵심 요약: 호스트는 목적지 IP를 확인한 후 ARP로 목적지 MAC 주소를 알아내고, 패킷을 MAC 주소가 포함된 이더넷 프레임에 담아 네트워크로 전송합니다.

이전 글에서는 네트워크의 기본 구조와 구성 요소, 네트워크의 범위에 따른 분류, 그리고 메시지 교환 및 전송 방식에 대해 알아보았습니다.

이번 포스팅에서는 네트워크의 작동 원리를 이해하기 위해 필요한 핵심 개념인 프로토콜, 네트워크 참조 모델, 캡슐화, PDU, 그리고 트래픽과 네트워크 성능 지표에 대해 살펴봅시다.

2. 프로토콜

프로토콜은 네트워크에 연결된 노드 간에 정보를 정확하게 주고받기 위해 서로 합의한 규칙이나 절차를 의미합니다. 서로 다른 통신 장치들이 원활하게 정보를 주고받기 위해서는 동일한 프로토콜을 따라야 하며, 우리가 인터넷을 이용하거나 파일을 전송할 수 있는 것도 상대 호스트와 같은 프로토콜을 사용하기 때문에 가능한 일입니다.

• IP는 패킷을 수신지까지 전달하기 위해 사용되는 프로토콜입니다.

• ARP는 192.168.1.1과 같은 형태의 IP 주소를 A1:B2:C3:D4:E5:F6과 같은 형태의 MAC 주소로 대응하기 위해 사용되는 프로토콜입니다.

• HTTPS는 HTTP와 비교해서 보안상 더 안전한 프로토콜입니다.

• TCP는 UDP에 비해 일반적으로 느리지만 신뢰성이 높은 프로토콜입니다.

위에서의 프로토콜 예시를 통해 알 수 있는 것은 저마다의 목적과 특징이 있다는 것입니다. 각 프로토콜의 특징을 잘 이해하면, 네트워크가 어떻게 동작하는지 훨씬 더 쉽게 파악할 수 있습니다.

3. 네트워크 참조 모델

통신이 일어나는 각 과정을 계층으로 나눈 구조를 네트워크 참조 모델이라고 합니다. 통신 과정을 계층으로 나눈 이유로는 크게 두 가지가 있습니다.

첫 번째로는, 네트워크 구성과 설계에 용이합니다.

각 계층이 수행해야 할 역할이 정해져 있으므로, 계층의 목적에 맞게 프로토콜과 네트워크 장비를 계층별로 구성할 수 있습니다. 물론 모든 프로토콜과 네트워크 장비가 참조 모델에 완벽하게 부합하는 것은 아니지만, 네트워크를 구성하고 설계할 때 중요한 가이드라인으로 네트워크 참조 모델이 활용됩니다.

두 번째로는, 네트워크 문제 진단과 해결에 용이합니다.

통신 과정에서 문제가 발생했을 때, 네트워크를 계층별로 나누어 점검하면 어느 단계에서 문제가 발생했는지 파악하기 쉬워집니다. 이러한 점에서 네트워크 참조 모델은 문제의 원인을 체계적으로 진단하고 해결하는 데에 도움이 됩니다.

다음으로 대표적인 네트워크 참조 모델인 OSI 모델과 TCP/IP 모델에 대해서 알아보겠습니다.

(1) OSI 모델

OSI 모델은 통신 과정을 7개의 계층으로 나눕니다. 하위 계층부터 순서대로 물리 계층, 데이터 링크 계층, 네트워크 계층, 전송 계층, 세션 계층, 표현 계층, 응용 계층으로 구성되어 있습니다.

• 1) 물리 계층 (Physical Layer) 1과 0으로 표현되는 비트 신호를 주고 받는 계층입니다. 비트 데이터를 통신 매체에 적합한 신호(전기, 빛, 전파 등)로 변환하여 전송합니다.

• 2) 데이터 링크 계층 (Data Link Layer) 물리 계층을 통해 주고 받는 데이터에 오류가 없는지 확인합니다. 또한, MAC 주소를 사용하여 같은 네트워크 내에서 송신자와 수신자를 식별할 수 있습니다. 전송 중 충돌이 발생할 수 있는 환경에서는 충돌을 감지하거나 회피하여 데이터가 안정적으로 전달되도록 합니다.

• 3) 네트워크 계층 (Network Layer) 메시지를 다른 네트워크에 속한 수신지까지 전달하는 계층입니다. IP 주소라는 주소 체계를 통해 통신하고자 하는 수신지 호스트와 네트워크를 식별하고, 원하는 수신지에 도달하기 위한 최적의 경로를 결정합니다.

• 4) 전송 계층 (Transport Layer) 신뢰성 있고 안정적인 데이터 전송을 보장하는 계층입니다. 데이터의 흐름을 조절하고, 전송 중 발생할 수 있는 오류를 검출 및 복구하여 데이터가 정확하게 전달되도록 합니다. 또한, 포트 번호를 사용해 여러 응용 프로그램을 구분하고 식별함으로써, 올바른 프로그램에 데이터가 전달되도록 합니다.

• 5) 세션 계층 (Session Layer) 통신하는 두 호스트 간의 연결(세션)을 관리하는 계층입니다. 세션을 생성, 유지, 종료하는 역할을 하여 통신이 원활하게 이루어지도록 돕습니다.

• 6) 표현 계층 (Presentation Layer) 서로 다른 시스템이 이해할 수 있도록 데이터 형식을 변환하는 계층입니다. 예를 들어, 문자 인코딩(UTF-8, ASCII) 변환, 데이터 압축, 암호화와 복호화 등을 수행하여 데이터가 올바르게 전달되고 해석될 수 있도록 돕습니다.

• 7) 응용 계층 (Application Layer) 사용자가 이용할 응용 프로그램에 다양한 네트워크 서비스를 제공합니다. 예를 들어, 웹 브라우저가 웹 페이지를 요청하는 HTTP 서비스, 이메일 송수신을 위한 SMTP 서비스, 파일 전송을 위한 FTP 서비스 등이 여기에 해당합니다.

(2) TCP/IP 모델

OSI 모델은 네트워크를 이론적으로 기술하고 이해할 때 사용하는 반면에 TCP/IP 모델은 이론보다는 실제 구현에 중점을 둔 네트워크 참조 모델입니다. 하위 계층부터 순서대로 네트워크 액세스 계층, 인터넷 계층, 전송 계층, 응용 계층으로 구성되어 있습니다.

• 1) 네트워크 액세스 계층 (Network Access Layer) OSI 모델의 데이터 링크 계층과 물리 계층 역할을 포함하며, 실제 네트워크 하드웨어와 데이터 전송을 담당합니다.

• 2) 인터넷 계층 (Internet Layer) OSI 모델의 네트워크 계층과 유사하며, IP 주소를 기반으로 한 패킷 전달과 라우팅을 담당합니다.

• 3) 전송 계층 (Transport Layer) OSI 모델의 전송 계층과 유사하며, 신뢰성 있는 데이터 전송과 흐름 제어, 오류 제어를 담당합니다.

• 4) 응용 계층 (Application Layer) OSI 모델의 세션 계층, 표현 계층, 응용 계층의 기능을 통합한 계층으로, 사용자 응용프로그램에 다양한 네트워크 서비스를 제공합니다.

4. 캡슐화

앞에서 학습한 프로토콜과 네트워크 참조 모델을 토대로 실제로 패킷이 어떻게 송수신되는지 알아봅시다.

패킷은 송신 과정에서 캡슐화가 이루어지고, 수신 과정에서 역캡슐화가 이루어집니다. 송신지 입장에서는 상위 계층 → 하위 계층 방향으로 데이터를 내려보내고, 수신지에서는 하위 계층 → 상위 계층 방향으로 데이터를 처리합니다.

(1) 캡슐화

캡슐화(Encapsulation)는 데이터를 전송할 때 각 계층에서 필요한 정보를 덧붙여가며 데이터를 감싸는 과정입니다.

• 1) 응용 계층에서 메시지를 생성합니다. 메시지는 패킷 단위로 송신됩니다.

  패킷은 헤더(Header)와 페이로드(Payload), 그리고 경우에 따라 트레일러(Trailer)를 포함하여 구성됩니다.

• 헤더*는 데이터 전달을 위한 제어 정보(예: 주소, 포트 번호 등)를 담고 있으며, 각 계층에서 추가됩니다. 페이로드는 실제로 전송하고자 하는 데이터로, 상위 계층에서 전달받은 패킷이 여기에 해당합니다. 트레일러는 주로 데이터 링크 계층에서 추가되며, 오류 검출 등의 기능을 수행합니다.

• 2) 각 계층을 내려가면서 해당 계층의 제어 정보를 헤더(Header)로 추가합니다.

• 3) 이 과정을 통해 최종적으로 프레임이 생성되어 네트워크를 통해 전송됩니다.

예: 응용 계층 데이터 → 전송 계층 (TCP 헤더 추가) → 인터넷 계층 (IP 헤더 추가) → 네트워크 인터페이스 계층 (MAC 헤더 및 트레일러 추가)

(2) 역캡슐화

역캡슐화(Decapsulation)는 수신 측에서 데이터를 받을 때, 각 계층에서 자신의 헤더를 제거하고 상위 계층에 전달하는 과정입니다.

• 4) 네트워크 인터페이스 계층에서 프레임을 수신합니다.

• 5) 각 계층은 자신에게 필요한 헤더만 읽고 제거한 후 상위 계층으로 전달합니다.

• 6) 최종적으로 응용 계층에 도달하면, 사용자가 이해할 수 있는 실제 데이터가 완성됩니다.

예: 네트워크 인터페이스 계층 (MAC 헤더 제거) -> 인터넷 계층 (IP 헤더 제거) -> 전송 계층 (TCP 헤더 제거) -> 응용 계층 (최종 데이터 처리)

이러한 과정을 거쳐서, 송신 측에서 생성된 데이터는 각 계층을 따라 헤더와 트레일러가 순차적으로 붙은 상태로 전송되며, 수신 측에서는 이 정보들을 하나씩 제거(역캡슐화)하면서 원래의 데이터로 복원합니다. 이처럼 캡슐화와 역캡슐화 과정은 데이터가 네트워크를 통해 정확하고 안전하게 전달되도록 보장하며, 계층별 역할 분담과 독립적인 설계를 가능하게 합니다.

5. PDU

각 계층에서 송수신되는 메시지의 단위를 PDU라고 합니다. 상위 계층에서 전달받은 데이터에 현재 계층의 프로토콜 헤더(및 트레일러)를 추가하면 현재 계층의 PDU가 됩니다.

전송 계층의 PDU는 TCP 프로토콜이 사용되었을 경우에는 세그먼트(Segment), UDP 프로토콜이 사용되었을 경우에는 데이터그램(Datagram)이 됩니다.

6. 네트워크 성능 지표

네트워크 성능을 평가할 때는 데이터를 주고받는 양과 속도가 중요한 기준이 됩니다. 이 중 하나인 트래픽은 일정 시간 동안 네트워크를 통해 전달되는 데이터의 양을 뜻합니다. 특정 노드(장치나 서버)에 트래픽이 집중되면, 해당 노드가 처리해야 할 데이터가 많아져 과부하가 발생할 수 있습니다. 이 과부하는 네트워크 속도 저하나 지연을 일으켜 전체 성능에 영향을 미치게 됩니다.

그렇다면 네트워크의 성능을 평가하는 지표로는 어떤 것들이 있을까요?

(1) 처리율

단위 시간당 네트워크를 통해 실제로 전송에 성공한 정보량을 말합니다.

• 처리율은 네트워크가 얼마나 효율적으로 데이터를 전달하는지를 보여줍니다.

• 대역폭과 달리, 네트워크 상태나 트래픽 상황에 따라 처리율은 변동될 수 있습니다.

• 예를 들어, 대역폭이 1Gbps라 해도 장애나 혼잡이 있으면 실제 처리율은 그보다 낮을 수 있습니다.

  (2) 대역폭

  단위 시간 동안 통신 매체를 통해 송수신할 수 있는 최대 정보량을 말합니다.

• 네트워크가 이론적으로 지원할 수 있는 최대 속도를 나타냅니다.

(3) 패킷 손실

송수신되는 패킷이 손실된 상황을 말합니다.

• 네트워크 과부하, 장비 장애, 노드의 처리 지연 등으로 인해 발생합니다.

• 손실된 패킷은 재전송이 필요해 전체 네트워크 지연과 성능 저하를 일으킵니다.

• 손실률이 높으면 데이터 신뢰성에 문제를 일으키게 됩니다.

7. 마무리

이번 포스팅에서는 네트워크의 작동 원리를 이해하는 데 꼭 필요한 핵심 개념들을 살펴보았습니다.

이전 포스팅에서 다룬 네트워크의 기본 구조와 함께 이번 내용을 정리해 두면, 네트워크 전반에 대한 기초적인 배경지식을 쌓을 수 있을 것입니다.

이번 포스팅에서는 네트워크의 기본 구조와 이를 구성하는 요소들, 네트워크의 범위에 따른 분류, 그리고 메시지 교환 방식과 전송 방식의 차이점을 체계적으로 살펴보겠습니다. 이를 통해 네트워크의 핵심 개념을 이해하고, 보다 복잡한 네트워크 기술을 학습하는 데 필요한 배경지식을 갖출 수 있게 됩니다.

2. 네트워크의 기본 구조

네트워크란 여러 장치가 서로 연결되어 정보를 주고받을 수 있는 통신망입니다. 이 통신망의 모양은 그래프의 형태를 띄고 있는데, 그래프란 노드와 노드를 연결하는 간선으로 이루어진 자료 구조입니다.

출처: geeksforgeeks.org - Types of Node Devices in a Computer Network

모든 네트워크는 '노드', 노드를 연결하는 '간선', 노드 간 주고받는 '메시지'로 구성됩니다. 노드는 정보를 주고받을 수 있는 장치 (그림에서의 디바이스), 간선은 정보를 주고받을 수 있는 유무선의 통신 매체(그림에서 디바이스 간의 선)를 말합니다.

네트워크의 기본 구조를 정리하자면, 네트워크는 가장자리 노드인 호스트, 중간 노드인 네트워크 장비, 노드들을 연결하는 간선인 통신 매체, 노드들이 주고받는 정보인 메시지로 구성됩니다.

(1) 호스트

네트워크의 가장자리에 위치한 노드는 네트워크를 통해 흐르는 정보를 최초로 생성 및 송신하고, 최종적으로 수신하는 역할을 합니다. 우리가 일상에서 사용하는 네트워크 기기(데스크톱, 노트북, 스마트폰 등)의 대부분이 여기에 속한다고 봐도 무방합니다. 이러한 가장자리 노드를 네트워크에서는 호스트라고 부릅니다.

호스트의 대표적인 역할로는 서버와 클라이언트가 있습니다.

서버라는 용어는 "serve(제공하다)" 에서 비롯되었는데, 서비스를 제공하는 역할을 하는 호스트가 바로 서버입니다. 여기서 서비스는 파일, 웹 페이지, 메일 등이 있습니다.

클라이언트란 서버에게 서비스를 요청하고 그에 대한 응답을 제공받는 호스트입니다. 예를 들어, 여러분이 노트북에서 웹 브라우저를 열고 구글에 접속을 시도했다고 해 봅시다. 그럼 구글의 서버는 해당 요청을 받고, 그 요청에 맞는 웹 페이지를 여러분의 웹 브라우저에 전달합니다. 여기서 여러분의 노트북은 클라이언트로서 구글 서버에 웹 페이지를 요청하고, 그에 대한 응답을 제공받게 된 것입니다.

(2) 네트워크 장비

네트워크 노드는 호스트뿐만 아니라, 네트워크 가장자리에 위치하지 않은 중간 노드들도 있습니다. 이러한 중간 노드들을 네트워크 장비라고 하며, 대표적으로 이더넷 허브, 스위치, 라우터, 공유기 등이 있습니다. 네트워크 장비는 호스트 간 주고받는 정보를 목적지까지 안정적이고 안전하게 전송될 수 있도록 합니다.

(3) 통신 매체

위 그림에서 호스트와 네트워크 장비들이 간선으로 연결되어 있는 것을 확인할 수 있는데, 이렇게 각 노드를 연결하는 간선을 통신 매체라고 합니다. 이 통신 매체에는 노드들을 유선으로 연결하는 유선 매체, 무선으로 연결하는 무선 매체가 있습니다.

(4) 메시지

통신 매체로 연결된 노드가 주고받는 정보를 메시지라고 합니다. 메시지는 웹 페이지나 파일, 또는 이메일처럼 여러 형태로 존재할 수 있습니다.

3. 범위에 따른 네트워크의 분류

네트워크의 구성 범위는 한 기업이 될 수도 있고, 한 지역이 될 수도 있고, 국가가 될 수도 있습니다. 이처럼 네트워크의 구성 범위가 다양한 만큼, 네트워크를 범위에 따라 분류하는 기준이 존재합니다. 이러한 기준으로 LAN과 WAN이 있습니다.

(1) LAN

LAN은 Local Area Network로, 가까운 지역을 연결한 근거리 통신망을 의미합니다. 가정, 학교, 기업처럼 한정된 공간에서의 네트워크가 바로 LAN입니다.

(2) WAN

WAN은 Wide Area Network로, 먼 지역을 연결하는 광역 통신망을 의미합니다. 멀리 떨어진 LAN을 연결할 수 있는 네트워크가 바로 WAN입니다.

4. 메시지 교환 방식에 따른 네트워크 분류

호스트들은 네트워크에서 어떤 방식으로 메시지를 주고 받을까요? 회선 교환 방식과 패킷 교환 방식이 있습니다.

(1) 회선 교환 방식

회선 교환 방식은 메시지 전송로인 회선을 설정하고 이 경로를 통해 메시지를 주고받는 방식입니다. 회선 교환 네트워크에서는 호스트들이 메시지를 주고받기 전에 미리 두 호스트를 연결한 후, 연결된 경로로 메시지를 주고받습니다.

회선 교환 네트워크가 올바르게 동작하기 위해서는 호스트 간의 회선이 적절하게 설정되어야 하는데, 이를 수행하는 네트워크 장비로는 회선 스위치가 있습니다. 즉, 회선 스위치는 호스트 사이에 일대일 정소로를 확보하는 네트워크 장비입니다.

회선 교환 방식은 두 호스트 사이에 연결을 확보한 후에 메시지를 주고받는 특성 덕분에 주어진 시간 동안 전송되는 정보의 양이 비교적 일정하다는 장점이 있습니다. 반면, 회선의 이용 효율이 낮아질 수 있다는 단점이 있는데요. 어떤 호스트가 메시지를 주고받기 위해 특정 회선을 사용해야 하는데, 그 회선을 다른 호스트가 이미 점유하고 있다면 다른 호스트는 이를 사용할 수 없습니다. 이 때문에 회선이 점유되어 있는 동안 데이터가 전송되지 않는다면 회선 자원이 낭비되는 것입니다.

예를 들어, A와 B가 전화 통화를 하고 있다면 통신 회선이 일대일로 연결되기 때문에 A나 B는 동시에 다른 사람인 C와 통화할 수 없습니다. 이때 A와 B가 통화 중임에도 불구하고 아무 말도 하지 않는다면, 그 시간 동안 회선 자원이 낭비되는 셈입니다.

(2) 패킷 교환 방식

패킷 교환 방식은 앞서 언급한 회선 교환 방식의 단점을 보완한 방식으로, 메시지를 작은 단위인 패킷으로 나누어 전송하는 방식입니다. 패킷으로 나누어진 메시지들은 수신지로 도달한 뒤 재조립됩니다. 현재 대부분의 네트워크에서 패킷 교환 방식을 사용하고 있습니다.

사전에 설정된 경로만으로 통신하는 회선 교환 방식과는 달리, 패킷 교환 방식은 정해진 경로만으로 메시지를 송수신하지 않습니다. 때문에 회선 교환 방식보다 회선의 이용 효율이 상대적으로 높습니다. 패킷으로 나누어진 메시지는 다양한 중간 노드를 거칠 수 있는데, 이때 중간 노드인 패킷 스위치는 패킷의 송수신지 주소를 확인하여, 수신지까지 도달할 최적의 경로를 결정합니다. 대표적인 패킷 스위치 네트워크 장비로는 라우터와 스위치가 있습니다. 라우터는 서로 다른 네트워크 간에 데이터를 전달하며, 목적지 IP 주소를 기반으로 최적의 경로를 찾아 패킷을 전송하는 장비이고, 스위치는 같은 네트워크 내부에서 장치들 간의 데이터를 목적지 MAC 주소를 기반으로 빠르고 효율적으로 전달하는 장비입니다.

패킷은 주로 헤더(Header), 페이로드(Payload), 트레일러(Trailer)의 세 부분으로 구성됩니다. 헤더에는 송수신지 주소, 순서 정보, 헤더 자체의 무결성을 확인하기 위한 제어 정보 등이 담겨 있으며, 페이로드는 실제로 전송하고자 하는 데이터가 담긴 부분입니다. 마지막으로 트레일러에는 전송된 데이터의 오류 검출을 위한 정보가 포함되어, 데이터가 올바르게 수신되었는지 확인하는 데 사용됩니다.

5. 주소와 송수신지 유형에 따른 전송 방식

패킷의 헤더에 담기는 대표적인 정보로는 주소가 있습니다. 주소는 송수신지를 특정하는 정보를 의미합니다. 이러한 주소에는 IP 주소와 MAC 주소가 있습니다.

이렇게 송수신지를 특정할 수 있는 주소가 있다면 송수신지 유형에 따라 다양한 방식으로 메시지를 보낼 수 있게 됩니다. 이러한 송수신지 유형에 따른 대표적인 전송 방식으로는 유니캐스트와 브로드캐스트가 있습니다.

(1) 유니캐스트

유니캐스트는 가장 일반적인 형태의 송수신 방식으로, 하나의 수신지에 메시지를 전송하는 방식입니다. 송신지와 수신지가 일대일로 메시지를 주고받는 경우입니다.

(2) 브로드캐스트

브로드캐스트는 자신을 제외한 네트워크상의 모든 호스트에게 전송하는 방식입니다. 브로드캐스트가 전송되는 범위를 브로드캐스트 도메인이라고 합니다. 즉, 브로드캐스트의 수신지는 브로드캐스트 도메인이며 이는 자신을 제외한 네트워크상의 모든 호스트를 말합니다.

이외에도 네트워크 내의 동일 그룹에 속한 호스트에게만 전송하는 방식인 멀티캐스트, 네트워크 내의 동일 그룹에 속한 호스트 중 가장 가까운 호스트에게 전송하는 방식인 애니캐스트 등 다양한 방식이 있습니다.

네트워크의 기본 구조와 핵심 개념을 다음 포스팅에서 이어서 다루겠습니다.

개발자는 단순히 코드를 잘 작성하는 것뿐만 아니라, 그 코드가 어떻게 다른 시스템과 소통하는지도 이해할 필요가 있습니다. 그 중심에는 컴퓨터 네트워크가 있습니다.

이 글에서는 컴퓨터 네트워크의 기본 개념부터, 개발자가 왜 네트워크를 알아야 하는지, 그리고 어떤 상황에서 네트워크 지식이 활용되는지까지 알아보겠습니다.

2. 네트워크란?

우리가 사용하는 스마트폰, 노트북, 데스크탑 등은 주변 기기들과 유선 혹은 무선으로 연결되어 데이터를 주고받습니다.
이 장치들은 서로 직접 연결되기도 하고, 다른 장치를 거쳐 간접적으로 연결되기도 합니다.

이처럼 수많은 장치들이 서로 얽혀 정보를 주고받을 수 있도록 구성된 구조를 네트워크라고 합니다. 마치 거미줄처럼 장치들이 촘촘히 연결되어 있는 구조라고 보면 이해하기 쉽습니다.

여러 장치들이 네트워크를 통해 서로 연결되면 주변의 장치하고만 정보를 주고 받는 것이 아니라, 네트워크와 연결된 지구 반대편에 있는 장치와도 정보를 주고받을 수 있습니다. 이를 가능하게 하는 기술이 바로 인터넷입니다.

인터넷은 여러 네트워크를 연결한 '네트워크의 네트워크'를 의미합니다.

3. 개발자가 네트워크를 알아야 하는 이유

일상적으로 실행하는 많은 프로그램들은 하나의 장치 안에서만 실행되기보다는 네트워크를 통해 다른 장치와 상호 작용하며 실행되는 경우가 많습니다.
프로그램이 네트워크를 통해 다른 장치와 상호 작용하며 실행되는 경우가 많다는 것은, 그만큼 개발자가 네트워크를 이용하는 프로그램을 개발하는 경우가 많다는 것을 의미합니다.

개발자가 네트워크를 제대로 이해해야 하는 것도 이러한 이유 때문입니다.

그렇다면 개발자는 네트워크 지식을 어디에, 어떻게 활용하게 될까요?

(1) 프로그램을 만드는 데 네트워크 지식이 활용됩니다.

웹 애플리케이션을 개발하거나 서버와 통신하는 기능을 구현하다 보면, 단순히 기능만 구현하는 코드로는 해결하기 어려운 상황들이 생깁니다.
예를 들어, 사용자가 로그인할 때 데이터를 서버에 안전하게 전송하고, 서버는 그 요청에 대해 성공 여부를 명확하게 알려줘야 하는데, 이 과정에서 적절한 HTTP 메서드와 상태 코드를 제대로 사용하는 것이 매우 중요합니다.
이런 상황에서 네트워크에 대한 이해가 중요한 역할을 하며, 이를 바탕으로 더 안정적이고 효율적인 통신을 구현할 수 있습니다.

또한 Django, Spring, Express 같은 프레임워크를 사용할 때도

• 라우팅 처리
• 쿠키와 세션 관리
• CORS 설정
• 포트 번호 설정

등과 같은 기능을 제대로 사용하려면 네트워크에 대한 개념을 이해하고 있어야 합니다.

REST API, 웹 소켓, OAuth 인증 등도 네트워크 프로토콜 위에서 동작하므로,
TCP/UDP, DNS, HTTPS와 같은 네트워크 지식이 뒷받침되어야 기능을 올바르게 이해하고 구현할 수 있습니다.

(2) 프로그램을 유지 보수하기 위해 네트워크 지식이 필요합니다.

서비스를 운영하다 보면 다음과 같은 예상치 못한 문제들이 생깁니다:

• 클라이언트에서 서버로 요청이 전달되지 않음
• 특정 포트가 막혀 통신이 되지 않음
• 갑자기 웹 서버가 응답하지 않음
• DNS 설정 오류로 인해 도메인이 작동하지 않음

이때 네트워크 구조와 동작 원리를 알고 있다면, 원인을 빠르게 파악하고 적절한 조치를 취할 수 있게 됩니다.
단순히 "통신에 문제가 있어요"라고 말하는 수준을 넘어서, 실제로 어디에서 문제가 발생했는지 분석하고 해결할 수 있는 능력이 생기는 것입니다.

4. 마무리

개발자는 단순히 코드를 작성하는 것에 그치지 않고, 그 코드가 네트워크 위에서 어떻게 동작하고 상호작용하는지 이해해야 더 나은 프로그램을 만들 수 있습니다. 네트워크에 대한 이해는 단지 기능 구현을 넘어, 서비스의 안정성과 유지 보수성을 높이는 데 큰 도움이 됩니다.

다음 포스팅에서는 네트워크에서의 필수 배경지식들에 대해 알아보겠습니다. 이해를 돕기 위해 최대한 쉽게 풀어 설명할 예정이니, 함께 학습해 보시기 바랍니다!

복잡한 네트워크를 구성할 때, 어떻게 하면 최소 비용으로 모든 지점을 연결할 수 있을까? 이 문제를 해결하기 위한 핵심 개념이 최소 신장 트리(MST, Minimum Spanning Tree)입니다. MST는 그래프의 모든 정점을 연결하되, 불필요한 연결 없이 최소 비용만으로 구성된 네트워크를 의미합니다.

이번 포스팅에서는 MST의 개념과 대표적인 알고리즘(크루스칼과 프림), 그리고 실제 구현 방법까지 함께 살펴보겠습니다.

2. MST란?

MST (Minimum Spanning Tree)는 무방향 가중치 그래프에서 모든 정점을 연결하면서, 간선 가중치의 합이 최소가 되도록 구성한 트리를 의미합니다.

조건은 다음과 같습니다:

• 모든 정점이 연결되어야 함
• 트리이므로 사이클이 없어야 함
• 간선 가중치 합이 최소여야 함

MST를 구하는 대표적인 알고리즘으로 크루스칼과 프림 알고리즘이 있습니다.

3. MST 구현 방법

3-1. 크루스칼 알고리즘 (Kruskal)

크루스칼 알고리즘은 간선을 중심으로 최소 신장 트리를 만들어 나가는 방식입니다.

우선 모든 간선을 가중치 기준으로 오름차순 정렬한 뒤, 가장 가중치가 작은 간선부터 하나씩 선택하면서 사이클이 생기지 않도록 주의하여 연결합니다.

이때 사이클 여부를 효율적으로 판단하기 위해 유니온 파인드(Union-Find) 자료구조를 사용합니다.

import java.util.*;

public class KruskalMST {
    static int[] parent;

    static class Edge implements Comparable<Edge> {
        int from, to, weight;

        Edge(int from, int to, int weight) { 
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }

    static int find(int x) {  
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static void union(int a, int b) { 
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot != bRoot) {
            parent[bRoot] = aRoot;
        }
    }

    public static void main(String[] args) {
        int n = 5; // 정점 개수
        List<Edge> edges = Arrays.asList(
            new Edge(1, 2, 3),
            new Edge(1, 3, 2),
            new Edge(2, 3, 1),
            new Edge(2, 4, 4),
            new Edge(3, 5, 6)
        );

        Collections.sort(edges);

        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        int total = 0;
        for (Edge e : edges) {
            if (find(e.from) != find(e.to)) {
                union(e.from, e.to);
                total += e.weight;
            }
        }

        System.out.println("최소 신장 트리 가중치 합: " + total);
    }
}

다음은 구현 과정입니다.

1. 그래프의 모든 간선을 모읍니다. 연결 정보(정점1, 정점2, 가중치)를 간선 리스트에 저장합니다.

2. 간선들을 가중치 기준으로 오름차순 정렬합니다. 가장 작은 가중치부터 하나씩 선택할 수 있도록 정렬합니다.

3. 유니온-파인드(Disjoint Set)를 준비합니다. 각각의 정점이 자신을 부모로 갖도록 초기화하여, 나중에 사이클 여부를 빠르게 판단할 수 있게 합니다.

4. 정렬된 간선을 하나씩 보면서, 두 정점이 연결되어 있지 않다면 연결합니다. 이때 서로 다른 집합에 속해 있는지(= 사이클이 생기지 않는지)를 find()로 확인합니다. 연결해도 괜찮다면 union()을 통해 합칩니다.

5. 간선을 연결할 때마다 가중치를 누적합니다. 최종적으로 모든 정점을 연결하게 되면, 누적된 가중치 합이 바로 최소 신장 트리의 비용입니다.

3-2. 프림 알고리즘 (Prim)

프림 알고리즘은 정점을 중심으로 최소 신장 트리를 확장해 나가는 방식입니다.

처음에 아무 정점 하나에서 시작해서, 현재 방문한 정점과 인접한 간선 중 가장 작은 것을 선택해 트리에 포함시킵니다. 이를 반복하여 모든 정점이 연결될 때까지 진행합니다.

우선순위 큐(PriorityQueue)를 사용하여 가장 가중치가 작은 간선을 빠르게 선택합니다.

import java.util.*;

public class PrimMST {
    static class Node implements Comparable<Node> {
        int to, weight;

        Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node other) {
            return this.weight - other.weight;
        }
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 무방향 간선 추가
        graph.get(1).add(new Node(2, 3));
        graph.get(2).add(new Node(1, 3));
        graph.get(1).add(new Node(3, 2));
        graph.get(3).add(new Node(1, 2));
        graph.get(2).add(new Node(3, 1));
        graph.get(3).add(new Node(2, 1));
        graph.get(2).add(new Node(4, 4));
        graph.get(4).add(new Node(2, 4));
        graph.get(3).add(new Node(5, 6));
        graph.get(5).add(new Node(3, 6));

        boolean[] visited = new boolean[n + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0));

        int total = 0;
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            if (visited[current.to]) continue;
            visited[current.to] = true;
            total += current.weight;

            for (Node next : graph.get(current.to)) {
                if (!visited[next.to]) {
                    pq.add(next);
                }
            }
        }

        System.out.println("최소 신장 트리 가중치 합: " + total);
    }
}

다음은 구현 과정입니다.

1. 인접 리스트 형태로 그래프를 구성합니다. 각 정점마다 연결된 간선들을 저장합니다. 무방향 그래프이므로 양쪽 모두 추가합니다.

2. 임의의 시작 정점을 정하고, 우선순위 큐에 넣습니다. 처음에는 연결된 간선이 없으므로 가중치 0으로 시작 정점을 큐에 넣습니다.

3. 우선순위 큐에서 가장 가중치가 작은 간선을 꺼냅니다. 만약 해당 정점이 이미 방문된 정점이라면 무시하고, 아니라면 방문 처리합니다.

4. 선택된 간선의 가중치를 누적하고, 해당 정점에서 뻗어나가는 모든 간선을 큐에 추가합니다. 단, 아직 방문하지 않은 정점들만 대상으로 합니다.

5. 모든 정점을 방문할 때까지 반복합니다. 우선순위 큐가 빌 때까지 진행하면, 최소 신장 트리의 비용이 완성됩니다.

4. MST vs 다익스트라 vs 플로이드-워셜

5. 백준 문제 추천

6. 마무리

최소 신장 트리는 여러 지점을 가장 효율적으로 연결하는 과정입니다. 불필요한 연결을 줄이고, 꼭 필요한 간선만으로 전체를 하나로 묶는 것이 핵심이죠. 모든 노드를 최소 비용으로 연결해야 하는 상황에서 반드시 알아야 할 개념입니다.

MST를 구하는 방법에는 앞서 다룬 것처럼, 크루스칼 알고리즘에서 간선을 중심으로 확장하는 방법과 프림 알고리즘에서 정점을 중심으로 확장하는 방법이 있습니다. 그래프의 구조와 조건에 따라 더 적합한 알고리즘을 선택하는 것이 중요합니다.

유니온 파인드(Union-Find)는 서로소 집합(Disjoint Set) 자료구조라고도 하며, 여러 개의 원소를 여러 집합으로 나누어 관리합니다. 이를 통해 두 원소가 같은 집합에 속하는지 빠르게 확인할 수 있고, 서로 다른 집합을 하나로 합치는 연산도 효율적으로 처리할 수 있습니다.

2. 유니온 파인드란?

• union(x, y): 두 원소 x와 y가 속한 집합을 합친다.
• find(x): 원소 x가 속한 집합의 대표자(루트)를 찾는다.

집합의 대표자(루트)를 찾음으로써 두 원소가 같은 집합인지 확인할 수 있습니다.

유니온 파인드는 다음과 같은 문제에서 매우 유용합니다.

• 네트워크 연결 여부 확인: 두 컴퓨터가 같은 네트워크 상에 있는지 확인
• 친구 관계 그래프: 두 사람이 친구 그룹에 속해 있는지 확인
• 사이클 탐지: 그래프에서 사이클이 형성되는지 여부 검사
• 최소 신장 트리(MST) 알고리즘: 크루스칼 알고리즘에서 사이클 여부 확인에 필수

예시 ) 사람들의 친구 관계를 관리할 때 각 사람을 노드로 보고, 친구 관계를 union 연산으로 묶어 나가면, 특정 두 사람이 같은 친구 그룹에 있는지 find 연산을 통해 쉽게 판단할 수 있습니다.

3. 유니온 파인드 핵심 개념

3-1. 경로 압축 (Path Compression)

find(x) 연산을 수행할 때, x의 부모 노드를 따라 루트 노드를 찾게 되는데, 이 과정에서 방문한 모든 노드의 부모를 루트로 직접 연결합니다.
이렇게 하면 모든 노드가 루트에 직접 연결되기 때문에, 다음 find 연산은 거의 한 번만에 루트를 찾을 수 있게 됩니다.

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 경로 압축
    }
    return parent[x];
}

예시 ) 초기 상태: 1 → 2 → 3 (3이 루트) find(1)을 호출하면: 1 → 3, 2 → 3 으로 갱신됨 (모두 루트로 직접 연결됨)

3-2. 높이 또는 크기 기반 합치기 (Union by Rank / Size)

두 트리를 합칠 때, 트리의 높이(랭크)나 노드 개수(크기)를 기준으로 작은 쪽을 큰 쪽에 붙입니다.
이렇게 하면 전체 트리의 최대 깊이가 불필요하게 증가하는 것을 방지할 수 있어, find 연산 시 루트까지 올라가는 시간이 줄어듭니다.
즉, 트리가 한쪽으로 길게 자라는 것을 막아 시간 복잡도를 O(α(N))(거의 상수 시간)으로 유지할 수 있습니다.

public void union(int x, int y) {
    int xRoot = find(x);
    int yRoot = find(y);

    if (xRoot == yRoot) return;

    if (rank[xRoot] < rank[yRoot]) {
        parent[xRoot] = yRoot;
    } else {
        parent[yRoot] = xRoot;
        if (rank[xRoot] == rank[yRoot]) {
            rank[xRoot]++;
        }
    }
}

예시 ) x 트리의 높이가 1이고 y 트리의 높이가 2일 때, x를 y에 붙이면 전체 트리의 높이는 그대로 2로 유지됩니다. 반대로 y를 x에 붙이면 트리의 높이가 3으로 불필요하게 증가하게 되어, 탐색 시간이 더 오래 걸리게 됩니다.

4. 유니온 파인드 구현 방법 (Java)

import java.util.*;

public class UnionFind {
    static int[] parent;
    static int[] rank;  // 각 노드의 랭크(트리 높이) 저장

    public static void main(String[] args) {
        int n = 7; // 노드 개수
        parent = new int[n + 1];
        rank = new int[n + 1];

        // 초기화: 각 노드는 자기 자신을 부모로, 랭크는 0으로 초기화
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }

        // union 연산 수행
        union(1, 2);
        union(2, 3);
        union(4, 5);
        union(6, 7);
        union(5, 6);

        // 같은 집합인지 확인
        System.out.println(find(1) == find(3)); // true
        System.out.println(find(1) == find(4)); // false
        System.out.println(find(5) == find(7)); // true
    }

    // find 연산 (경로 압축 적용)
    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // union 연산 (Union by Rank 적용)
    static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return;

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
    }
}

다음은 union 연산의 동작 과정입니다.

1. union(1, 2)

• find(1) → 1, find(2) → 2 (서로 다른 집합)
• rank[1] = rank[2] 이므로 1을 루트 노드로 설정하고 2를 연결, rank[1]++

  parent: [0, 1, 1, 3, 4, 5, 6, 7] rank: [0, 1, 0, 0, 0, 0, 0, 0]

2. union(2, 3)

• find(2) → 1, find(3) → 3
• rank[1] > rank[3] 이므로 3을 {1, 2} 집합에 붙임

  parent: [0, 1, 1, 1, 4, 5, 6, 7] rank: [0, 1, 0, 0, 0, 0, 0, 0]

3. union(4, 5)

• find(4) → 4, find(5) → 5
• rank[4] = rank[5] 이므로 4를 루트 노드로 설정하고 5를 연결, rank[4]++

  parent: [0, 1, 1, 1, 4, 4, 6, 7] rank: [0, 1, 0, 0, 1, 0, 0, 0]

4. union(6, 7)

• find(6) → 6, find(7) → 7
• rank[6] = rank[7] 이므로 6을 루트 노드로 설정하고 7을 연결, rank[6]++

  parent: [0, 1, 1, 1, 4, 4, 6, 6] rank: [0, 1, 0, 0, 1, 0, 1, 0]

5. union(5, 6)

• find(5) → 4, find(6) → 6
• rank[4] = rank[6] 이므로 4를 루트 노드로 설정하고 6을 연결, rank[4]++

  parent: [0, 1, 1, 1, 4, 4, 4, 6] rank: [0, 1, 0, 0, 2, 0, 1, 0]

결과적으로 union() 연산을 통해 {1, 2, 3}, {4, 5, 6, 7} 두 개의 집합이 형성되고, find() 연산을 통해 두 노드가 같은 집합에 속하는지 확인할 수 있게 됩니다.

5. 백준 문제 추천

6. 마무리

유니온 파인드는 서로소 집합을 관리하고 연결 여부를 확인하는 데 아주 유용한 알고리즘입니다. 특히, 크루스칼 알고리즘에서 MST(최소 신장 트리)를 구현할 때 핵심적으로 사용합니다.

find()의 경로 압축과 union()의 루트 합치기 방식은 트리의 깊이를 최소화하여 시간 복잡도를 거의 상수 시간에 가깝게 최적화하는 기법입니다. 이 두 가지 최적화를 통해 여러 번의 find()와 union() 연산이 효율적으로 처리됩니다.

따라서 유니온 파인드는 MST뿐만 아니라 그래프에서 연결성, 사이클 검출 등 다양한 분야에서 폭넓게 쓰이며, 경로 압축과 루트 합치기 최적화 기법은 이러한 연산을 매우 빠르게 해주는 핵심 기술입니다.

👉 다음 포스팅에서는 유니온 파인드를 기반으로 한 최소 신장 트리(MST)에 대해 자세히 다뤄보겠습니다.

위상 정렬(Topological Sort)은 방향 그래프에서 사이클이 없는 경우에 사용할 수 있는 알고리즘으로,
모든 간선 (u → v)에 대해 u가 v보다 먼저 오도록, 정점들을 일정한 순서로 나열하는 방법입니다.

쉽게 말해, 선행 조건이 있는 작업들의 순서를 정하는 알고리즘입니다.

예시)

1. 작업 A가 작업 B보다 먼저 끝나야 할 때
2. 수강 과목을 순서대로 들어야 할 때

2. 위상 정렬이란?

출처: medium.com - Graph Theory Algorithms

다음은 그림에 대한 동작 과정입니다.

1. 진입 차수가 0인 E부터 탐색을 시작합니다.

   • 진입 차수가 0인 노드가 여러 개일 경우,
     알파벳 순으로 먼저 처리하기 위해 우선순위 큐를 사용합니다.

2. E → B, F 간선을 따라 B와 F의 진입 차수를 1씩 감소시킵니다.
   B의 진입 차수가 0이 되어 큐에 추가됩니다.

3. B를 꺼내고 → A, C의 진입 차수를 감소시킵니다.
   진입 차수가 0이 된 A, C가 큐에 추가됩니다.

4. 이후 과정은 동일한 패턴의 반복입니다.

   • 큐에서 알파벳 순으로 노드를 꺼냅니다.
   • 해당 노드가 가리키는 노드들의 진입 차수를 감소시킵니다.
   • 진입 차수가 0이 된 노드는 다시 큐에 추가됩니다.
   • 이 과정을 큐가 빌 때까지 반복합니다.

위 과정을 반복하면, 그래프 내 모든 노드들이 선후 관계에 맞게 차례대로 정렬됩니다. 특히, 알파벳 순서대로 처리하기 위해 우선순위 큐를 사용했기 때문에 노드들이 E B A C F D I K H J G 순서로 정렬되는 것을 확인할 수 있습니다.

특정 순서 조건이 없다면 우선순위 큐 대신 일반 큐를 써도 무방합니다.

2-1. 위상 정렬을 이해하려면?

큐와 진입 차수를 이용한 BFS 방식을 구현하기 위해서는 진입 차수의 이해가 필요합니다.

진입 차수란?

어떤 정점(노드)으로 들어오는 간선(화살표)의 개수를 의미합니다.

• 예를 들어, A → B라는 간선이 있다면, 노드 B의 진입 차수는 1입니다.

• 위상 정렬에서는 진입 차수가 0인 노드부터 처리합니다.

• 사이클이 없는 방향 그래프에서는
  항상 진입 차수가 0인 노드가 최소 1개 이상 존재합니다.

• 이 노드를 시작점으로 삼아 위상 정렬을 수행할 수 있습니다.

3. 위상 정렬 구현 방법

3-1. BFS 기반 방식 (큐와 진입 차수를 이용)

import java.util.*;

public class TopologicalSort {
    public static void main(String[] args) {
        int n = 11;
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 단방향 간선 추가 (그림에서 A ~ K까지를 1 ~ 11로 변환)
        graph.get(1).add(4); inDegree[4]++;
        graph.get(2).add(1); inDegree[1]++;
        graph.get(2).add(3); inDegree[3]++;
        graph.get(3).add(7); inDegree[7]++;
        graph.get(4).add(7); inDegree[7]++;
        graph.get(5).add(2); inDegree[2]++;
        graph.get(5).add(6); inDegree[6]++;
        graph.get(6).add(4); inDegree[4]++;
        graph.get(6).add(8); inDegree[8]++;
        graph.get(8).add(10); inDegree[10]++;
        graph.get(9).add(8); inDegree[8]++;
        graph.get(9).add(11); inDegree[11]++;
        graph.get(10).add(7); inDegree[7]++;
        graph.get(11).add(8); inDegree[8]++;

        // 특정 순서를 요구하지 않는 위상 정렬에서는 큐를 사용
        // 그림에서는 번호가 작은 노드부터 먼저 처리하기 때문에 우선 순위 큐를 사용
        Queue<Integer> queue = new PriorityQueue<>();

        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        List<Integer> result = new ArrayList<>();

        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);

            for (int next : graph.get(current)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.add(next);
                }
            }
        }

        if (result.size() != n) {
            System.out.println("사이클이 존재합니다.");
        } else {
            StringBuilder sb = new StringBuilder();
            for (int num : result) {
                sb.append((char) (num + 'A' - 1)).append(" ");
            }
            System.out.println("위상 정렬 결과: " + sb.toString().trim());
        }
    }
}

3-2. DFS 기반 방식

public class DFSTopologicalSort {
    static boolean[] visited;
    static Deque<Integer> stack = new ArrayDeque<>();
    static List<List<Integer>> graph;

    public static void dfs(int node) {
        visited[node] = true;
        for (int next : graph.get(node)) {
            if (!visited[next]) {
                dfs(next);
            }
        }
        stack.push(node); // 나중에 방문한 걸 먼저 출력
    }

    public static void main(String[] args) {
        int n = 11;
        graph = new ArrayList<>();
        visited = new boolean[n + 1];

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 단방향 간선 추가 (그림에서 A ~ K까지를 1 ~ 11로 변환)
        graph.get(1).add(4); 
        graph.get(2).add(1); 
        graph.get(2).add(3); 
        graph.get(3).add(7); 
        graph.get(4).add(7);
        graph.get(5).add(2);
        graph.get(5).add(6);
        graph.get(6).add(4); 
        graph.get(6).add(8);
        graph.get(8).add(10);
        graph.get(9).add(8);
        graph.get(9).add(11);
        graph.get(10).add(7);
        graph.get(11).add(8);

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }

        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
}

3-3. BFS 방식과 DFS 방식의 차이점

위상 정렬을 할 때 두 방식은 같은 그래프라도 결과가 다르게 나올 수 있습니다.

BFS 방식에서는 진입 차수가 0인 노드들을 큐에 넣고 처리하는데,

• 일반 큐(Queue)를 사용하면 노드가 큐에 들어온 순서대로 처리되어, 특정한 순서를 보장하지 않습니다.
• 다만, 진입 차수가 0인 노드가 항상 하나뿐이고, 큐에 담긴 노드가 처리되는 동안 항상 큐의 크기가 1이라면, 일반 큐를 쓰더라도 결과는 항상 동일하게 나옵니다. 즉, 이 경우엔 우선순위 큐를 쓰지 않아도 순서가 보장됩니다.

  선후 관계 문제에서 진입 차수가 0인 노드가 여러 개일 경우, 탐색 순서가 일관적이지 않으므로 명확한 순서를 정할 수 없다는 점을 유의해주세요.

• 반면 우선순위 큐(PriorityQueue)를 사용하면 노드 번호가 작은 것부터 차례대로 처리되기 때문에, 번호 순서에 맞는 정렬 결과를 얻을 수 있습니다.
• 또한, BFS 방식은 진입 차수를 이용하기 때문에 사이클이 존재하는 경우 모든 노드를 탐색하지 못하게 되며, 이를 통해 사이클 유무를 자동으로 탐지할 수 있습니다.

DFS 방식은

• 한 방향으로 깊게 탐색하며 노드를 쌓기 때문에, 방문 순서에 따라 결과가 달라질 수 있습니다.
• 또한 사이클 탐지의 경우, 방문 상태를 3단계(미방문, 방문중, 방문완료)로 별도 관리해야 하며, 현재 방문 중인 노드를 다시 만나면 사이클이 존재한다고 판단합니다.

결론적으로, BFS 방식이 위상 정렬을 구현하는 데 직관적입니다. 또한, 사이클 탐지가 필요한 경우에도 BFS 방식의 구현이 더 간단합니다.

반면, DFS 방식은 위상 정렬 과정에서 추가적인 정보나 경로 추적 등 다양한 응용이 가능하므로, 두 방식 모두 상황에 맞게 유용하게 활용할 수 있습니다.

4. 위상 정렬 vs 다익스트라 vs 플로이드-워셜

5. 백준 문제 추천

6. 마무리

위상 정렬은 그래프가 사이클이 없을 때, 그리고 선후관계가 있을 때 사용 가능한 알고리즘입니다.

큐와 진입 차수를 이용한 BFS 방식은 직관적이며,
DFS 기반 방식은 재귀를 활용해 간결하게 구현할 수 있습니다.

위상 정렬을 적용하기 전에는 방향 그래프에 사이클이 존재하는지 확인하는 과정이 매우 중요합니다. 사이클이 존재하면 위상 정렬이 불가능하므로, 사이클 유무를 미리 체크하는 습관을 들이는 것이 좋습니다.

👉 그래프 탐색 알고리즘이 익숙하지 않다면 [이전 포스트]들을 참고해보세요!

플로이드-워셜(Floyd-Warshall) 알고리즘은 모든 정점에서 모든 정점까지의 최단 거리를 구할 수 있는 알고리즘입니다.

다익스트라는 단일 시작점에서 출발하는 최단 거리만 구할 수 있고,
벨만-포드는 음수 간선과 사이클 탐지에 유용하지만 단일 시작점 기준입니다.

반면, 플로이드-워셜은 모든 정점 쌍 간의 최단 거리를 구할 수 있어 그래프 내 모든 경로 정보를 필요로 하는 문제에서 효과적입니다.

입력 그래프가 정점 수가 적고 간선 수가 많을 때 적합합니다.
간선에 음수 가중치는 허용되지만, 음수 사이클은 허용되지 않습니다.

2. 플로이드-워셜이란?

플로이드-워셜은 ‘모든 정점 쌍 사이의 최단 거리’를 한 번에 구하는 방법입니다. 각 정점을 거쳐 가는 경로를 차례대로 확인하면서 최단 거리를 갱신해 나가는 방식으로 동작합니다.

출처: medium.com - Understanding Floyd-Warshall Algorithm

1. 4 x 4 크기의 dist[][] 배열을 INF 값으로 초기화합니다.

2. 자기 자신으로 가는 비용을 0으로 설정합니다.

dist[i][i] = 0;

3. k, i, j 세 정점을 잡고, 현재 i → j로 가는 최단 거리보다 i → k + k → j를 거쳐 가는 경로가 더 짧다면, 해당 경로로 최단 거리를 갱신합니다.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

이 과정을 k = 1 ~ n까지 모든 정점에 대해 반복하면, 최종적으로 모든 정점 쌍 간의 최단 거리가 dist[][] 배열에 저장됩니다.

3. 플로이드-워셜 구현 (Java)

import java.util.*;

public class FloydWarshallExample {
    static final int INF = Integer.MAX_VALUE / 2; // Integer.MAX_VALUE 사용하면 overflow 위험 존재

    public static void main(String[] args) {
        int n = 4; // 정점 수
        int[][] dist = new int[n][n];

        // 초기화
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0; // 자기 자신으로 가는 비용은 0
        }

        // 간선 정보 (예시: 단방향)
        // 같은 간선의 정보가 여러 개일 경우 최솟값 반영
        dist[0][1] = 1;
        dist[1][2] = 3;
        dist[0][2] = 2;
        dist[2][3] = -2;

        // 알고리즘 실행
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 출력
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print((dist[i][j] == INF ? "INF" : dist[i][j]) + " ");
            }
            System.out.println();
        }
    }
}

3-1. 구현 핵심 요약

플로이드-워셜 알고리즘을 구현할 때 핵심이 되는 흐름은 다음과 같습니다.

1. dist[i][j] 배열을 만들어, 정점 i에서 j로 가는 최단 거리를 저장합니다.
   초기에는 i에서 j로 가는 간선이 있다면 그 가중치로, 없다면 충분히 큰 값(INF)으로 설정합니다. 여기서 INF 값으로 Integer.MAX_VALUE를 사용하면 덧셈 과정에서 오버플로우가 발생할 수 있으므로,

INF는 Integer.MAX_VALUE / 2 정도로 큰 값으로 사용합니다.

2. 세 정점 i, j, k를 잡고, 정점 k를 거쳐 i에서 j로 가는 경로가
   현재 알고 있는 최단 거리보다 더 짧은지 확인하면서 거리를 업데이트합니다.
   이 과정을 다음과 같은 식으로 표현할 수 있습니다: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

   3. 위 작업을 모든 정점 쌍 (i, j)에 대해, 그리고 모든 정점 k에 대해 반복합니다.

이 과정을 통해, 모든 정점 쌍 간의 최단 거리를 효율적으로 구할 수 있으며, 음수 가중치가 있어도 동작한다는 장점이 있습니다.

4. 다익스트라 vs 벨만-포드 vs 플로이드-워셜

5. 백준 문제 추천

6. 마무리

플로이드-워셜은 모든 정점 쌍 간의 최단 경로를 한 번에 구할 수 있는 강력한 알고리즘입니다. 구현이 간단하면서도, 음수 간선까지 처리할 수 있다는 장점이 있어 그래프 전체의 경로 정보를 빠르게 파악해야 하는 상황에서 유용합니다.

하지만 시간 복잡도가 $O(N^3)$으로, 정점의 수가 많아질수록 성능이 급격히 저하될 수 있기 때문에 상황에 따라 다익스트라, 벨만-포드, 플로이드-워셜 중 가장 적절한 알고리즘을 선택하는 것이 중요합니다.

👉 다익스트라와 벨만-포드 알고리즘이 익숙하지 않다면 [이전 포스트]를 참고해 주세요!

벨만-포드(Bellman-Ford) 알고리즘은 음의 가중치가 포함된 그래프에서도 최단 거리를 구할 수 있는 알고리즘입니다.

다익스트라는 가중치가 모두 양수일 때만 동작하지만, 벨만-포드는 음수 간선이 있어도 사용 가능합니다. 또한 음수 사이클(계속 돌면 비용이 줄어드는 경우)도 판별할 수 있어, 다양한 문제에서 유용하게 활용됩니다.

이 글에서는 벨만-포드 알고리즘의 개념, 구현, 다익스트라와의 차이점, 그리고 실전 문제 활용까지 단계별로 정리해보겠습니다.

2. 벨만-포드란?

벨만-포드는 모든 간선 정보를 반복적으로 확인하면서 최단 거리를 갱신하는 방식입니다.

"최대 (정점 수 - 1)번인 모든 간선을 반복적으로 확인하면, 최단 거리를 보장할 수 있다." 를 전제로 합니다.

마지막 반복 이후에도 최단 거리가 갱신된다면, 음수 사이클이 존재함을 탐지할 수 있습니다.

출처: memgraph.com - Graph Search Algorithms: Developer's Guide

아래는 그림과 같이 최단 거리를 구하는 과정입니다.

1. 시작 정점 A의 거리를 0으로 설정하고, 나머지 정점들은 모두 무한대(∞)로 초기화합니다.

최단 거리 배열은 A:0, B:∞, C:∞, D:∞, E:∞가 됩니다.

2. 첫 번째 반복입니다.
   모든 간선을 차례로 검사하며 최단 거리를 갱신합니다.

• A → B 간선 검사: B까지 거리를 0 + 4 = 4로 갱신합니다.
• D → A 간선 검사: A의 최단 거리는 0이므로 변화가 없습니다.
• B → D 간선 검사: D까지 최단 거리를 4 + (-1) = 3으로 갱신합니다.
• D → E 간선 검사: E까지 최단 거리를 3 + 8 = 11로 갱신합니다.
• B → E 간선 검사: E까지 최단 거리를 4 + (-3) = 1로 갱신합니다.
• C → B 간선 검사: B의 최단 거리 4보다 크므로 변화가 없습니다.
• E → C 간선 검사: C까지 최단 거리를 1 + 6 = 7로 갱신합니다.

첫 번째 반복 후 최단 거리 배열은 A:0, B:4, C:7, D:3, E:1이 됩니다.

3. 두 번째 반복입니다.
   모든 간선을 다시 검사하지만, 거리 배열에 변화가 없습니다.
   이후 반복(세 번째, 네 번째)에서도 거리가 더 이상 갱신되지 않습니다.

4. 마지막 반복(네 번째)을 마친 뒤 음수 사이클을 탐지합니다. 한 번 더 모든 간선을 검사하여 거리 갱신 여부를 확인합니다.

갱신이 없으므로, 음수 사이클이 존재하지 않음을 확인할 수 있습니다.

최종적으로 각 정점까지의 최단 거리는 A:0, B:4, C:7, D:3, E:1 로 계산됩니다.

2-1. 벨만-포드를 이해하려면?

벨만-포드는 음수 가중치가 있는 그래프에서 최단 거리를 찾을 수 있는 알고리즘입니다. 이를 정확히 이해하려면 아래와 같은 개념을 알고 있어야 합니다.

벨만-포드는 이 개념들을 바탕으로 모든 간선을 여러 번 반복해서 확인하며, 각 정점까지의 최단 거리를 점차 갱신해 나가는 방식으로 동작합니다.

최단 경로는 최대 (정점 수 - 1) 개의 간선으로 이루어질 수 있기 때문에, 모든 간선을 (정점 수 - 1) 번 반복해서 검사하며 최단 거리 배열을 업데이트합니다. 이 과정에서 더 짧은 경로가 발견되면 즉시 최단 거리를 갱신합니다.

만약 마지막 반복 후에도 최단 거리 갱신이 일어난다면, 이는 음수 사이클이 존재한다는 뜻으로, 최단 거리가 무한히 작아질 수 있어 정확한 결과를 구할 수 없음을 의미합니다.

벨만-포드는 이러한 음수 사이클의 존재 여부를 판단할 수 있는 기능을 갖추고 있습니다.

2-2. 벨만-포드의 특징

• 벨만-포드는 음수 가중치가 포함된 그래프에서 정확하게 최단 거리를 계산할 수 있습니다.

• 음수 사이클이 있으면 최단 거리가 무한히 작아져서 정의될 수 없는데, 벨만-포드는 이를 감지할 수 있습니다.

• 다익스트라 알고리즘에 비해 구현이 좀 더 복잡하고 연산 시간이 더 오래 걸리지만, 음수 가중치가 포함된 상황에서는 필수적인 알고리즘입니다.

3. 벨만-포드 구현 (Java)

import java.util.*;

public class BellmanFordExample {
    static class Edge {
        int from, to, cost;

        Edge(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }

    static final int INF = Integer.MAX_VALUE;
    static int n, m;
    static List<Edge> edges;
    static long[] dist;

    public static void main(String[] args) {
        n = 5; // 정점 수 (A~E)
        m = 7; // 간선 수

        edges = new ArrayList<>();
        dist = new long[n + 1];

        // 거리 초기화
        Arrays.fill(dist, INF);
        dist[1] = 0; // 시작 노드: A (1번)

        // 간선 정보 (from, to, cost)
        edges.add(new Edge(1, 2, 4));   // A -> B (4)
        edges.add(new Edge(4, 1, 2));   // D -> A (2)
        edges.add(new Edge(2, 4, -1));  // B -> D (-1)
        edges.add(new Edge(4, 5, 8));   // D -> E (8)
        edges.add(new Edge(2, 5, -3));  // B -> E (-3)
        edges.add(new Edge(3, 2, 3));   // C -> B (3)
        edges.add(new Edge(5, 3, 6));   // E -> C (6)

        boolean hasCycle = bellmanFord(1); // 시작 노드 A (1번)

        if (hasCycle) {
            System.out.println("음수 사이클이 존재합니다.");
        } else {
            for (int i = 1; i <= n; i++) {
                System.out.println(i + "번 노드까지 최단 거리: " + (dist[i] == INF ? "도달 불가" : dist[i]));
            }
        }
    }

    static boolean bellmanFord(int start) {
        for (int i = 0; i < n - 1; i++) {
            for (Edge e : edges) {
                if (dist[e.from] != INF && dist[e.to] > dist[e.from] + e.cost) {
                    dist[e.to] = dist[e.from] + e.cost;
                }
            }
        }

        // n번째 반복에서 갱신되면 음수 사이클 존재
        for (Edge e : edges) {
            if (dist[e.from] != INF && dist[e.to] > dist[e.from] + e.cost) {
                return true;
            }
        }

        return false;
    }
}

3-1. 구현 핵심 요약

벨만-포드 알고리즘을 구현할 때 핵심이 되는 흐름은 다음과 같습니다.

1. 최단 거리 배열을 무한대(INF)로 초기화합니다.
   이는 아직 어떤 노드에도 도달하지 않았음을 의미합니다.

2. 시작 노드의 최단 거리를 0으로 설정합니다.

3. 전체 간선을 V-1번 반복하여 확인합니다.
   각 반복마다 모든 간선을 순회하며,
   현재 노드를 거쳐 가는 경로가 더 짧은 경우 최단 거리를 갱신합니다.

4. V번째 반복에서 갱신이 발생하는지 확인합니다.
   이 단계에서 거리가 또 갱신된다면, 이는 음수 사이클이 존재함을 의미합니다.

이러한 과정을 통해, 출발 노드에서 모든 노드까지의 최단 거리를 구할 수 있으며,
음수 가중치가 포함된 그래프에서도 사용할 수 있다는 점이 특징입니다.

4. 다익스트라 vs 벨만-포드

5. 백준 문제 추천

6. 마무리

벨만-포드는 음수 간선과 음수 사이클까지 고려할 수 있는 유일한 최단 경로 알고리즘입니다.

다익스트라에 비해 느리지만, 음수 가중치가 있는 복잡한 그래프 문제에서는 벨만-포드 알고리즘을 사용해야 합니다.

📌 벨만-포드를 정확히 이해하고 구현할 수 있다면, 음수 가중치와 음수 사이클 탐지 등 다양한 그래프 문제에서 응용력을 크게 높일 수 있을 것입니다.

👉 아직 다익스트라가 익숙하지 않다면, 이전 [다익스트라 완전 정복 포스트]를 참고해 보세요!

다익스트라(Dijkstra)는 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 데 가장 널리 쓰이는 알고리즘입니다.
BFS와는 다르게 간선에 가중치가 있을 때도 사용 가능하며, 코딩 테스트에서 자주 등장합니다.

이번 포스팅에서는 다익스트라 알고리즘의 개념, 구현, BFS와의 차이점, 그리고 실전 문제 활용까지 단계별로 살펴보겠습니다

2. 다익스트라란?

다익스트라는 우선순위 큐(최소 힙) 를 활용해 가중치가 있는 그래프의 최단 거리를 효율적으로 계산하는 알고리즘입니다.

출처: medium.com - Path Finding Algorithms

예시) 어떤 도시에서 출발해 다른 도시로 이동한다고 할 때, 각 길(간선)의 거리(가중치)가 다를 수 있습니다.
이때 가장 적은 비용으로 목표 지점에 도달하는 경로를 찾는 것이 바로 다익스트라입니다.

아래는 그림과 같이 최단 거리를 구하는 과정입니다.

1. 먼저, 시작 노드인 A에서 출발합니다. A에서 갈 수 있는 노드는 B(거리 4), C(거리 1)입니다. B까지의 최단 거리를 4, C까지의 최단 거리를 1로 저장합니다.

2. 다음으로, 시작점에서 가장 가까운 노드인 C(거리 1)를 선택합니다. C에서 연결된 노드는 D(거리 2), F(거리 6)입니다. A → C → D는 거리 1 + 2 = 3이므로, D까지의 최단 거리를 3으로 저장합니다. A → C → F는 거리 1 + 6 = 7이므로, F까지의 최단 거리를 7로 저장합니다.

3. C 노드에서 가까운 거리로 도달 가능한 D를 방문합니다. D에서는 E까지의 거리는 4입니다. A → C → D → E의 경로는 거리 3 + 4 = 7이므로, E까지의 최단 거리를 7로 저장합니다.

4. 이제 A -> B(거리 4)를 방문합니다. B에서 갈 수 있는 노드는 D(거리 3), E(거리 8)입니다. 하지만 D는 이미 최단 거리가 3으로 저장되어 있으므로, 갱신할 필요가 없습니다. E 역시 최단 거리가 7으로 저장되어 있기 때문에 그대로 둡니다.

*A -> B -> D와 A -> B -> E의 경로는 D, E 까지 도달하는 모든 경로 중에서 최단 거리가 아니므로, A -> B를 거치는 모든 경로는 최단 경로에서 제외됩니다. *

5. 이후에는 D에서 가까운 E(거리 7)를 방문합니다. E에서는 G(거리 2)로 갈 수 있습니다. A → C → D → E → G의 경로는 거리 7 + 2 = 9이므로, G까지의 최단 거리는 9로 저장됩니다.

6. 마지막으로 F(거리 7)를 방문합니다. F에서도 G(거리 8)로 갈 수 있지만, A → C → F → G는 거리 7 + 8 = 15로, 이미 구한 G까지의 거리 9보다 크기 때문에 최단 거리를 갱신하지 않습니다.

2-1. 다익스트라를 이해하려면?

다익스트라는 가중치가 있는 그래프에서 최단 거리를 구하는 알고리즘입니다. 이를 정확히 이해하려면 아래와 같은 개념을 알고 있어야 합니다.

다익스트라는 이 개념들을 바탕으로 우선순위 큐를 이용해 가장 적은 비용부터 하나씩 탐색하며, 각 경로를 지나면서 더 짧은 거리가 발견되면 즉시 갱신하는 방식으로 동작합니다.

2-2. 다익스트라의 특징

• 다익스트라는 간선의 가중치가 음수가 아닌 그래프에서만 정확하게 동작합니다.
  음수 가중치가 포함된 경우에는 벨만-포드 알고리즘을 사용해야 합니다.

• BFS보다 알고리즘 구조는 더 복잡하지만, 정확한 비용 기반의 거리 계산이 가능합니다.

• 한 번의 실행으로 모든 정점까지의 최단 거리를 계산할 수 있어, 다양한 경로 탐색 문제에서 유용하게 활용됩니다.

3. 다익스트라 구현 방법 (Java)

import java.util.*;

public class DijkstraExample {
    static class Node implements Comparable<Node> {
        int index, cost;

        Node(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.cost, other.cost); // 비용이 적은 순으로 정렬
        }
    }

    static List<List<Node>> graph;
    static int[] dist;
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int n = 7; // A, B, C, D, E, F, G 7개 노드

        graph = new ArrayList<>();
        dist = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
            dist[i] = INF;
        }

        // 단방향 그래프에서의 간선 정보 추가
        // A부터 G까지의 각 노드를 인덱스 1~7으로 적용
        graph.get(1).add(new Node(2, 4));
        graph.get(1).add(new Node(3, 1));
        graph.get(2).add(new Node(4, 3));
        graph.get(2).add(new Node(5, 8));
        graph.get(3).add(new Node(4, 2));
        graph.get(3).add(new Node(6, 6));
        graph.get(4).add(new Node(5, 4));
        graph.get(5).add(new Node(7, 2));
        graph.get(6).add(new Node(7, 8));

        dijkstra(1); // 1번 노드에서 시작

        for (int i = 1; i <= n; i++) {
            System.out.println(i + "번 노드까지 최단 거리: " + (dist[i] == INF ? "도달 불가" : dist[i]));
        }
    }

    static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[start] = 0;
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();

            // 이미 더 짧은 경로로 방문된 경우 무시
            if (current.cost > dist[current.index]) continue;

            for (Node neighbor : graph.get(current.index)) {
                int newCost = dist[current.index] + neighbor.cost;
                if (newCost < dist[neighbor.index]) {
                    dist[neighbor.index] = newCost;
                    pq.offer(new Node(neighbor.index, newCost));
                }
            }
        }
    }
}

3-1. 구현 핵심 요약

다익스트라 알고리즘을 구현할 때 핵심이 되는 흐름은 다음과 같습니다.

1. 최단 거리 배열을 무한대(INF)로 초기화합니다.
   이는 아직 어떤 노드에도 도달하지 않았음을 의미합니다.

2. 시작 노드의 최단 거리를 0으로 설정하고, 우선순위 큐에 넣습니다.

3. 이후, 우선순위 큐에서 가장 비용이 적은 노드를 꺼내어 해당 노드의 인접 노드들을 확인합니다.

4. 현재 노드를 거쳐 인접 노드로 가는 비용이 기존에 기록된 최단 거리보다 작으면, 해당 값을 갱신하고 인접 노드를 큐에 다시 넣습니다.

5. 이러한 과정을 큐가 빌 때까지 반복하면, 출발 노드에서 모든 노드까지의 최단 거리를 구할 수 있습니다.

4. BFS vs 다익스트라

참고: V = 정점(노드)의 수, E = 간선의 수

5. 백준 & 프로그래머스 문제 추천

6. 마무리

다익스트라는 가중치 그래프에서 최단 거리를 구하는 데 가장 적합한 알고리즘입니다.

BFS와 비교해 조금 더 복잡하지만, 문제 해결 능력을 높이기 위해 반드시 익혀야 할 알고리즘입니다.

📌 다익스트라를 정확히 이해하고 구현할 수 있다면, 이후 벨만-포드, 플로이드-워셜 등 다른 최단 경로 알고리즘도 쉽게 접근할 수 있을 것입니다.

👉 아직 BFS가 익숙하지 않다면, 이전 [BFS 완전 정복 포스트]를 참고해 보세요!

BFS(Breadth-First Search)는 DFS와 함께 가장 기초이자 중요한 그래프 탐색 알고리즘입니다.
최단 거리 문제, 단계별 탐색, 미로 탈출 등에서 필수적으로 활용되며, DFS와는 다른 방식으로 동작합니다.

이 글에서는 BFS의 개념부터 구현, DFS와의 차이, 실전 문제 활용까지 정리해 보겠습니다.

2. BFS란?

BFS는 그래프를 너비 우선으로 탐색하는 알고리즘입니다.
즉, 시작 정점에서 가까운 노드부터 먼저 방문한 뒤, 점점 멀리 있는 노드를 탐색합니다.
이를 위해 큐(Queue) 자료구조를 사용하여 탐색 순서를 관리합니다.

출처: medium.com - A quick explanation of DFS & BFS

예시) 미로에서 출발 지점에서 가까운 길부터 차례대로 살펴보는 방식과 유사합니다. 먼저 한 칸 거리의 길을 전부 확인하고, 그 다음 두 칸 거리, 세 칸 거리 순으로 탐색을 확장해 나갑니다. 출구에 도달했을 때 그 경로는 최단 경로가 됩니다.

2-1. BFS를 이해하려면?

BFS는 그래프에서 너비를 우선으로 탐색하는 알고리즘입니다. 이를 이해하기 위해서는 먼저 그래프와 관련된 기본 개념을 알고 있어야 합니다.

BFS는 이 개념들을 바탕으로 큐를 이용해 인접한 정점들을 순서대로 방문합니다.

3. BFS 구현 방법 (Java)

import java.util.*;

public class BFSExample {
    static List<Integer>[] graph;
    static boolean[] visited;

    public static void main(String[] args) {
        int n = 9;
        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 간선 추가
        graph[1].addAll(List.of(2, 3, 4));
        graph[2].addAll(List.of(1, 5));
        graph[3].addAll(List.of(1, 6, 7));
        graph[4].addAll(List.of(1, 8));
        graph[5].add(2);
        graph[6].addAll(List.of(3, 9));
        graph[7].add(3);
        graph[8].add(4);
        graph[9].add(6);

        bfs(1); // 1번 노드부터 탐색 시작
    }

    static void bfs(int start) {
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.pollFirst();
            System.out.print(node + " ");

            List<Integer> neighbors = graph[node];
            Collections.sort(neighbors); // 작은 번호부터 방문하도록 정렬

            for (int next : graph[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.addLast(next);
                }
            }
        }
    }
}

아래는 BFS 구현 동작 과정입니다.

1. 시작 노드부터 가까운 노드부터 차례대로 탐색합니다.
2. 큐(Queue) 자료구조를 사용하여 탐색 순서를 보장합니다. (큐는 먼저 들어온 노드가 먼저 나오는 선입선출 방식이므로, 최단 거리나 단계별 탐색에 유용합니다.)
3. 각 노드는 한 번만 방문되며, 방문한 노드는 다시 큐에 넣지 않습니다.
4. 탐색이 끝날 때까지 큐에 노드가 남아 있다면 다음 인접 노드를 탐색합니다.
   • 4-1. 만약 큐에 노드가 남아 있지만, 이미 원하는 조건(예: 최단 거리)이 만족되었다면, 더 이상 탐색을 진행하지 않고 탐색을 멈춥니다.

💡 큐(Queue) 덕분에 단계별 탐색이 자연스럽게 이루어지며, 탐색 순서가 확실히 보장됩니다.

❗ 단점: 큐에 저장할 노드가 많으면 메모리 사용량이 많아질 수 있습니다.

3-1. 시간 및 공간 복잡도

참고: V = 정점(노드)의 수, E = 간선의 수

4. DFS vs BFS 차이

DFS는 모든 경로를 깊이 우선으로 탐색할 때 유용한 알고리즘입니다. 경우의 수를 모두 따지며 깊이 있는 탐색을 통해 문제를 해결합니다. 주로 백트래킹, 조합/순열, 트리 순회 등에 적합하며, 재귀나 스택 자료구조를 사용하여 탐색을 진행합니다.

BFS는 너비 우선으로 탐색하며 조건을 만족하는 가장 빠른 경로(최단 거리)를 찾을 때 적합한 알고리즘입니다. 시작점에서 가까운 노드부터 차례로 탐색하며 문제를 해결합니다. 큐(Queue)를 사용하여 탐색 순서를 보장하며, 최단 거리나 단계별 탐색을 필요로 하는 문제에 매우 유용합니다.

5. 백준 & 프로그래머스 문제 추천

6. 마무리

BFS는 그래프를 단계적으로 탐색하며, 최단 거리 계산에 매우 유용한 알고리즘입니다.
DFS와 마찬가지로 코딩테스트에 자주 등장하며, 다양한 문제 풀이의 기본이 됩니다.

DFS는 깊이, BFS는 거리에 초점을 맞춘 탐색입니다.
DFS와 BFS 모두 충분히 연습해보고, 어떤 문제에서 어떤 탐색이 적절한지 판단하는 연습이 중요합니다.

👉 아직 DFS에 대해 익숙하지 않다면, 이전 DFS 완전 정복 포스트도 함께 확인해 보세요!

DFS (Depth-First Search) 는 그래프 탐색의 가장 기본이 되는 알고리즘입니다.
미로 탐색부터 백트래킹, 연결 요소 탐색, 트리 순회, 사이클 검출 등 다양한 문제에서 자주 등장합니다.

이 글에서는 DFS의 개념부터 시간/공간 복잡도, 재귀와 반복 구현 방식, 실전 문제 활용까지 다뤄보겠습니다.

2. DFS란?

DFS는 그래프를 깊이 우선으로 탐색하는 알고리즘입니다.
현재 정점에서 갈 수 있는 가장 깊은 곳까지 먼저 이동한 후, 막히면 되돌아가며(backtracking) 다른 경로를 탐색합니다.

출처: medium.com - A quick explanation of DFS & BFS

예시) 미로에서 한 방향으로 쭉 가보다가 막히면 돌아가서 다른 길을 찾는 방식입니다.

2-1. DFS를 이해하려면?

DFS는 주로 그래프(Graph) 자료구조를 탐색할 때 사용됩니다. 그래프는 다양한 문제에서 관계나 연결을 표현하는 데 쓰이며, 아래와 같은 요소들로 구성되어 있습니다:

이 개념들을 기반으로 DFS는 한 경로를 끝까지 따라가며 깊이 있게 탐색한 뒤, 다시 돌아와 다른 경로를 탐색하는 방식으로 작동합니다.
재귀 함수나 스택을 이용해 구현하는 경우가 많습니다.

3. DFS 구현 방법

3-1. 재귀 (Recursive) 방식

import java.util.*;

public class DFSExample {
    // 인접 리스트 선언
    static List<Integer>[] graph;
    // 방문 배열 선언
    static boolean[] visited;

    public static void main(String[] args) {
        int n = 9; // 노드 수
        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        // 인접 리스트 초기화
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 간선 추가
        graph[1].add(2);
        graph[2].add(1);
        graph[1].add(4);
        graph[4].add(1);
        graph[1].add(8);
        graph[8].add(1);
        graph[2].add(3);
        graph[3].add(2);
        graph[4].add(5);
        graph[5].add(4);
        graph[5].add(6);
        graph[6].add(5);
        graph[4].add(7);
        graph[7].add(4);
        graph[8].add(9);
        graph[9].add(8);

        dfs(1); // 1번 노드부터 탐색 시작
    }

    // 재귀 방식
    static void dfs(int node) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int next : graph[node]) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }
}

재귀 방식의 구현 동작 과정은 위의 이미지와 같습니다. 1 → 2 → 3 → (막힘) → 4 → 5 → 6 → (막힘) → 7 → (막힘) → 8 → 9

깊게 파고들고 막히면 한 단계씩 돌아와 다른 경로를 탐색합니다. 💡 재귀 구조 덕분에 백트래킹이 자연스럽게 구현됩니다.

❗단점으로는 깊이가 깊을 경우 StackOverflow 위험이 존재합니다.

3-2. 스택 (Stack) 반복문 방식

void dfsIterative(int start) {
    Deque<Integer> stack = new ArrayDeque<>(); // 스택 사용
    boolean[] visited = new boolean[graph.length]; 

    stack.push(start); // 시작 노드 스택에 추가

    while (!stack.isEmpty()) {
        int node = stack.pop(); // 스택에서 노드 꺼내기

        if (!visited[node]) {
            visited[node] = true; // 방문 표시
            System.out.print(node + " "); // 방문한 노드 출력

            // 인접 노드들을 내림차순으로 스택에 추가
            List<Integer> neighbors = graph[node];
            Collections.sort(neighbors, Collections.reverseOrder()); // 방문 순서 조정

            for (int next : neighbors) {
                if (!visited[next]) {
                    stack.push(next); // 방문하지 않은 노드 스택에 푸시
                }
            }
        }
    }
}

이 방식은 재귀 호출 없이 DFS를 구현하는 방법입니다. 명시적인 스택(Deque)을 사용해서 직접 호출 흐름을 제어합니다.

아래는 스택 방식의 구현 동작 과정입니다.

1. 탐색 시작 노드를 먼저 스택에 넣고, 스택에서 꺼낸 노드를 방문합니다.
2. 인접한 노드들을 스택에 넣되, 내림차순으로 정렬해 넣으면 작은 번호가 먼저 탐색됩니다. (스택은 후입선출이므로 뒤에 넣은 게 먼저 꺼내지기 때문입니다.)
3. 이미 방문한 노드는 다시 방문하지 않도록 체크합니다.

• 재귀 호출 대신 반복문과 스택을 사용해 StackOverflow 문제를 방지할 수 있습니다.
• 명시적인 스택을 사용하므로 호출 흐름이 눈에 보이며 디버깅이 쉬워집니다.
• 재귀 방식보다 메모리 사용량 제어에 유리합니다.

3-3. 시간 및 공간 복잡도

참고: V = 정점(노드)의 수, E = 간선의 수

4. DFS와 백트래킹의 차이

DFS와 백트래킹은 모두 재귀적 구조를 활용하는 탐색 기법이라는 공통점이 있지만, 문제 해결을 위한 목적과 전략 면에서 차이점이 존재합니다.

DFS는 모든 경로를 탐색하며 문제의 구조를 파악하거나 전체 상태를 순회할 때 유용합니다. 반면, 백트래킹은 탐색 중 조건에 맞지 않는 경우를 조기에 걸러내어(pruning) 필요한 경우만 탐색하기 때문에 불필요한 계산을 줄일 수 있는 효율적인 기법입니다.

즉, DFS는 탐색 그 자체에 중점을 두고, 백트래킹은 조건에 맞는 답을 찾기 위해 DFS를 응용한 전략이라고 볼 수 있습니다.

5. 백준 & 프로그래머스 문제 추천

6. 마무리

DFS는 단순한 그래프 탐색을 넘어서
다양한 문제 해결의 기반이 되는 알고리즘입니다.

• 재귀 방식은 구현이 간결하고 직관적이며,
• 반복문(스택) 방식은 메모리 관리에 유리합니다.

상황에 따라 두 방식 중 적절한 방법을 선택하는 것이 중요합니다.

또한, DFS는 탐색 그 자체뿐만 아니라,
백트래킹, 트리 순회, 사이클 탐지, 조합 생성 등 다양한 알고리즘 기법의 기반이 되므로,
초급 단계를 넘어 더 복잡한 문제를 풀기 위해서도 꼭 숙지해야 할 알고리즘입니다.

DFS 문제를 많이 접하고 직접 구현해보면서 내 것으로 만들면 실전 코딩테스트에서 훨씬 빠르고 정확하게 적용할 수 있을 것입니다.

다음 글에서는 DFS와 자주 비교되는 BFS (너비 우선 탐색) 에 대해 정리해보겠습니다.
DFS, BFS의 차이와 각 알고리즘 문제를 비교해 보며 실전 감각을 키워봅시다!