Baekjoon/DFS와 BFS

[백준] 1260 DFS와 BFS (실버2)

2023. 4. 17. 10:21

문제요약

나의 코드 및 설명

from collections import deque

def dfs(c):
    visited[c] = 1 #현재 정점 방문 처리
    ans_dfs.append(c) #정답 리스트에 현재 정점 추가
    for n in graph[c]: #현재 정점과 연결된 다른 정점들 살펴보기
        if visited[n] == 0: #만약 다른 정점이 아직 방문하지 않았다면
            dfs(n) #다음 정점 방문

def bfs(s):
    queue = deque() #큐 생성
    queue.append(s) #큐에 현재(시작) 정점 추가
    visited[s] = 1 #현재 정점 방문처리
    ans_bfs.append(s) #정답 리스트에 현재 정점 추가

    while queue: #정점이 하나도 없을때까지 
        c = queue.popleft() #큐에 먼저 들어간 순으로 꺼낸다
        for n in graph[c]: #꺼낸 정점과 연결된 다른 정점들 살펴보기
            if visited[n] == 0: #만약 다른 정점이 아직 방문하지 않았다면
                queue.append(n) #큐에 다른 정점들 삽입
                ans_bfs.append(n) #정답 리스트에 다른 정점들 삽입
                visited[n] = 1 #다른 정점들 방문처리

n,m,v = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)

#오름차순 정렬
for i in range(1, n+1):
    graph[i].sort()


visited = [0] * (n+1)
ans_dfs = []
dfs(v)

visited = [0] * (n+1)
ans_bfs = []
bfs(v)

print(" ".join(map(str, ans_dfs)))
print(" ".join(map(str, ans_bfs)))

피드백

백트래킹 문제 연습을 조금 했더니 이제 DFS 문제는 조금씩 보이는 것 같다. BFS가 부족한 것 같아서 더 공부해야할 것 같다.

'Baekjoon > DFS와 BFS' 카테고리의 다른 글

[백준] 1697 숨바꼭질 (실버1) / BFS  (0) 2023.04.21
[백준] 1012 유기농 배추 (실버2) / BFS (방문체크 위치 정확히!)  (0) 2023.04.21
[백준] 1926 그림 (실버1) / BFS, 런타임에러(ValueError) 해결  (0) 2023.04.19
[백준] 2667 단지번호붙이기 (실버1) / DFS  (0) 2023.04.17
[백준] 2178 미로 탐색 (실버1) / BFS  (0) 2023.04.17
'Baekjoon/DFS와 BFS' 카테고리의 다른 글
  • [백준] 1012 유기농 배추 (실버2) / BFS (방문체크 위치 정확히!)
  • [백준] 1926 그림 (실버1) / BFS, 런타임에러(ValueError) 해결
  • [백준] 2667 단지번호붙이기 (실버1) / DFS
  • [백준] 2178 미로 탐색 (실버1) / BFS
hellosonic
hellosonic
꾸준함hellosonic 님의 블로그입니다.
hellosonic
꾸준함
hellosonic
전체
오늘
어제
  • 분류 전체보기 (285)
    • SSAFY (4)
    • 프로그래머스 데브코스 (26)
    • Diary (1)
    • JavaScript (20)
    • ToyPJ (13)
      • Python-Django (13)
    • CS지식 (11)
      • 자료구조 (5)
      • 개발 상식 (2)
      • 네트워크 (4)
    • Baekjoon (141)
      • IM Level (57)
      • DFS와 BFS (21)
      • 백트래킹 (21)
      • DP (3)
      • 이분탐색 (4)
      • 구현 (14)
    • Programmers (13)
      • Lv1 (4)
      • Lv2 (9)
    • SWEA (SW Expert Academy) (52)
      • D1 (5)
      • D2 (7)
      • D3 (40)
    • 이코테 (4)
    • Grammar (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기
  • 관리자

공지사항

인기 글

태그

  • 자바스크립트
  • 국비지원교육
  • 파이썬 1946
  • 파이썬 2529
  • SWEA D3
  • 리액트 todolist
  • SWEA 파이썬
  • 자바스크립트 기본기
  • 구현
  • SWEA/D3
  • 이코테
  • javascript ux
  • 백준 14891
  • 파이썬 11478
  • 파이썬 1269
  • 그리디
  • 백준 5212
  • 프론트엔드 데브코스
  • 백준 2999
  • 프로그래머스
  • JS
  • SWEA D2
  • 백준
  • 백준 1157
  • 백준 18870
  • SWEA
  • 파이썬
  • 코딩부트캠프
  • 프로그래머스 데브코스
  • 파이썬 1436

최근 댓글

최근 글

hELLO · Designed By 정상우.
hellosonic
[백준] 1260 DFS와 BFS (실버2)
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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