[Python] 백준 1260번: DFS와 BFS

2023. 8. 18. 13:25· Koala - 11기/코딩테스트 준비 스터디

문제

https://www.acmicpc.net/problem/1260

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net



풀이

 

Dfs는 재귀, Bfs는 큐를 사용한다.(시간복잡도가 낮은 덱을 사용)

2차원 배열로 노드 연결여부를 구성. 최초 모든 연결을 False로 초기화

입력값에 따라 (시작노드,끝노드), (끝노드,시작노드)를 True로 만들어줌.(연결되었다)

visited1,visited2는 dfs,bfs의 방문기록 작성

깊이우선탐색, 너비우선탐색에서 조건문의 기준은

“방문하지 않았고, 연결이 되어있다면” 이다.

 

dfs는 재귀를 사용한다.

탐색을 시작할 정점의 번호 V부터 시작한다.

방문하지 않았고, 연결이 되어있다면 계속해서 재귀를 활용하여 깊이우선탐색을한다.

 

bfs는 큐(덱)을 사용한다

큐가 비어있지 않은동안 반복한다.

방문하지 않았고, 연결이 되어있다면 큐에 노드를 추가하고 방문처리해준다.


코드

import sys
input = sys.stdin.readline
from collections import deque

n,m,v=map(int,input().split())

#노드 연결여부
graph=[[False]* (n+1) for _ in range(n+1)]

for _ in range(m):
    a,b=map(int,input().split())
    graph[a][b]=True
    graph[b][a]=True

visited1=[False]* (n+1) #dfs방문기록
visited2=[False]* (n+1) #bfs방문기록


def dfs(v): #재귀
    visited1[v]=True
    print(v,end=' ')
    for i in range(1,n+1):
        if not visited1[i] and graph[v][i]: # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
            dfs(i)
def bfs(v): #큐
    q=deque([v]) #pop메서드의 시간복잡도가 O(1)로 작은 덱 내장 메서드 사용. 리스트사용시 poplast는 O(1)이지만, pop intermediate O(k)
    visited2[v] =True
    while q:
        v=q.popleft() #큐의 첫번째 값 꺼내기
        print(v,end=' ')
        for i in range(1,n+1):
            if not visited2[i] and graph[v][i]: ## 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
                q.append(i) #i 값(노드) 추가
                visited2[i] = True #i 값 방문 처리




dfs(v)
print()
bfs(v)

 

 

저작자표시 (새창열림)

'Koala - 11기 > 코딩테스트 준비 스터디' 카테고리의 다른 글

[백준/python3] 9657번 : 돌 게임 3  (0) 2023.08.19
[백준/Python] 9372번 상근이의 여행  (0) 2023.08.19
[C++] 백준 2606번: 바이러스  (0) 2023.08.16
[백준/python] 4949번 균형잡힌세상  (0) 2023.08.14
[백준/C++] 2346번 : 풍선 터뜨리기  (0) 2023.08.14
'Koala - 11기/코딩테스트 준비 스터디' 카테고리의 다른 글
  • [백준/python3] 9657번 : 돌 게임 3
  • [백준/Python] 9372번 상근이의 여행
  • [C++] 백준 2606번: 바이러스
  • [백준/python] 4949번 균형잡힌세상
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
Koala항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1888)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (42)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (35)
    • Koala - 20기 (0)
      • 코딩테스트 기초 스터디 (0)
      • 코딩테스트 심화 스터디 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • 백트래킹
  • 파이썬
  • dfs
  • dp
  • BFS
  • C++
  • 백준
  • BOJ

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[Python] 백준 1260번: DFS와 BFS
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.