본문 바로가기
728x90
SMALL

백준 DFS3

[백준] 4803번 : 트리 (파이썬) DFS / Union Find 문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 그래프에서 cycle이 존재하면 해당 그래프는 트리가 될 수 없다. 즉, 해당 문제는 어떠한 그래프가 주어졌을 때 cycle이 존재하는지의 여부를 구하고 트리의 갯수를 세는 문제이다. 이 문제는 union find나 dfs를 사용해서 풀 수 있다. 나는 이 문제를 총 2가지 방식으로 풀어보았다. (1) Union Find 이용 사실 이 문제는 .. 2024. 1. 15.
[백준] 1520번 : 내리막 길 (파이썬) DFS + Memorization 문제 (DFS로만 풀 시 시간초과) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net (1) 시간초과난 코드 (실패) # 내리막 길 (골드 3) / DFS-recursion (시간 초과) import sys r, c = map(int, sys.stdin.readline().split()) arr = [] visit = [[False] * c for _ in range(r)] dx = [-1, 0, 1, 0] dy = .. 2024. 1. 4.
[백준] 2178번 : 미로 탐색 (파이썬) 미로탐색 문제로, dfs나 bfs로 푸는 문제이다. 나는 bfs를 이용하여 문제를 해결하였다. 처음 내 코드 from collections import deque a,b = map(int,input().split()) visit = [[0]*b for _ in range(a)] for i in range(a): c = input() for j in range(b): visit[i][j] = int(c[j]) print(visit) #BFS queue = deque() dx = [-1,1,0,0] dy = [0,0,-1,1] length=0 for i in range(a): for j in range(b): if visit[i][j]==1: visit[i][j]=0 queue.append([i,j]) le.. 2023. 1. 23.
320x100
LIST

티스토리툴바