[백준] 1260번 DFS와 BFS - 파이썬(Python)

2021. 1. 18. 17:26· 알고리즘/문제풀이
목차
  1. 문제 (링크)
  2. 나의 풀이
728x90

문제 (링크)

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

 

1260번: DFS와 BFS

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

www.acmicpc.net

 

나의 풀이

from collections import deque
n, m, v = map(int, input().split())

matrix = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)

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

def bfs(v):
    queue = deque([v])
    visited[v] = True
    
    while queue:
        x = queue.popleft()
        print(x, end=' ')
        
        for i in range(len(matrix[x])):
            if matrix[x][i] == 1 and visited[i] == False:
                queue.append(i)
                visited[i] = True
                
    
def dfs(v):
    visited[v] = True
    print(v, end=' ')
    
    for i in range(len(matrix[v])):
        if visited[i] == False and matrix[v][i] == 1:
            dfs(i)

dfs(v)
visited = [False] * (n+1) # DFS를 한 번 실행하고 나면 visited가 모두 True로 바뀌기 때문에 수정해줌
print()
bfs(v)

 

일반적인 bfs와 dfs를 구현하는 방식을 이용했다.

 

하지만, 내가 지금까지 풀어본 방식은 인접여부를 0과 1로 지정하는 것이 아니라 직접 노드의 번호를 입력하는 방식이었기 때문에 코드를 작성하는데 어려움이 있었다.

 

알고리즘 공부할 때마다 막혔던 부분이 이 DFS / BFS 부분인데, 기초적이긴 해도 이걸 풀었다는게 너무 감격스럽다.

 

조금 더 힘내서 공부할 수 있을 것 같다.

저작자표시 (새창열림)

'알고리즘 > 문제풀이' 카테고리의 다른 글

[백준] 1920번 수 찾기 - 파이썬(Python)  (0) 2021.01.24
[백준] 2178번 미로탐색 - 파이썬(Python)  (0) 2021.01.19
[백준] 2798번 블랙잭 - 파이썬(Python)  (0) 2021.01.18
[백준] 10773번 제로 - 파이썬(Python)  (0) 2021.01.18
[백준] 11399번 ATM - 파이썬(Python)  (0) 2021.01.14
  1. 문제 (링크)
  2. 나의 풀이
'알고리즘/문제풀이' 카테고리의 다른 글
  • [백준] 1920번 수 찾기 - 파이썬(Python)
  • [백준] 2178번 미로탐색 - 파이썬(Python)
  • [백준] 2798번 블랙잭 - 파이썬(Python)
  • [백준] 10773번 제로 - 파이썬(Python)
SeongOnion
SeongOnion
서버는 꺼지지 않아요
SeongOnion
조무래기 코딩
SeongOnion
전체
오늘
어제
  • 분류 전체보기 (167)
    • 알고리즘 (81)
      • 이론 (8)
      • 문제풀이 (73)
    • 언어 (15)
      • Python (9)
      • JavaScript (1)
      • JAVA (5)
    • 데이터베이스 (5)
    • 프레임워크 (15)
      • Django (7)
      • Spring (8)
    • 그 외 공부 (38)
      • 운영체제 (1)
      • 자료구조 (14)
      • 네트워크 (5)
      • CS (2)
      • 기타 (7)
      • 트러블 슈팅 (9)
    • 프로젝트 (0)
    • 개발자취 (8)
    • 회고 (3)
    • 주저리주저리 (1)
    • 기타 (비개발) (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 프로그래머스
  • 스택
  • 웹
  • 트러블 슈팅
  • 장고
  • 정렬 알고리즘
  • 에라토스테네스의 체
  • spring
  • DP
  • 파이썬
  • 회고
  • 백준
  • 개발자
  • 큐
  • BFS
  • 소수
  • BFS/DFS
  • 데이터베이스
  • 알고리즘
  • 이진탐색
  • 오픈소스
  • 자바
  • 투 포인터 알고리즘
  • 그리디알고리즘
  • 브루트포스
  • 코딩
  • Django
  • DRF
  • 컨트리뷰트
  • 코딩테스트

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
SeongOnion
[백준] 1260번 DFS와 BFS - 파이썬(Python)
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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