•알고리즘(Algorithm )

[백준4803&파이썬] BFS를 활용하여 사이클을 찾아 트리여부를 확인하자

# 문제 백준 4803 트리 파이썬 풀이 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net # 코드 import sys from collections import deque from collections import defaultdict def solve(n,m) : ddict = defaultdict(list) for _ in range(m) : a,b = map(int,sys.stdin.readline().split()) ddict[a].append(b) ddict[b].append(a) ..

[백준16932&파이썬] BFS/DFS풀이에서 시간초과가 난다면 전처리방법이 있는지 고민해라

# 문제 백준 16932 모양만들기 파이썬 풀이 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net # 코드 ## 성공한 풀이 import sys from collections import deque N,M = map(int, sys.stdin.readline().split()) board = list() for _ in range(N) : line = list(map(int,sys.stdin.readline().split())) board.append(line) dirs = [ (-1,0), (0,1)..

[백준1325&파이썬] DFS+DP는 사이클이 없을때 사용 가능하다.

# 문제 백준 1325 효율적인 해킹 DFS 풀이 A / B를 해킹하면 A를 알 수 있다. # ###---시간초과 -> PyPy 제출 풀이 ---### counter = [-1] * (N+1) mmax = 0 for index in range(1,N+1) : visited = [False] * (N+1) stk = deque() stk.append(index) visited[index] = True cnt = 0 while len(stk) != 0 : cur = stk.pop() # 뽑기 for next in ddict[cur] : if visited[next] == False : cnt += 1 visited[next] = True stk.append(next) counter[index] = cnt m..

[백준2644&파이썬] 재귀식을 이용한 DFS 사용할때는 실패케이스에 대한 반환값을 생각하자

# 문제 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net # 코드 ## DFS import sys n = int(sys.stdin.readline()) # 전체 사람의 수 a,b = map(int,sys.stdin.readline().split()) # 촌수를 계산해야하는 a,b m = int(sys.stdin.readline()) # 관계의 개수 ddict = [ [] * 1 for _ in range(n+1)] # 인접리스트 만들기 visit = [False] * (n+1) for i ..

[백준11725&파이썬] BFS와 DFS에서 그래프 인접리스트의 활용

# 문제 백준 11725 트리의 부모찾기 파이썬 풀이 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net # 코드 import sys from collections import deque from collections import defaultdict N = int(sys.stdin.readline().strip()) ddict = defaultdict(list) result = [-1] * (N+1) for i in range(N-1) : a,b = map(int,sys.stdin.readline().strip().split()) ddict[a].append(b) ddict[..

[백준1520&파이썬] DFS에 메모이제이션을 곁들여서 시간초과를 해결하자

# 문제 백준 1520 내리막길 파이썬 풀이 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net # 코드 ## 성공한 코드 import sys M, N = map(int,sys.stdin.readline().split()) # M : 행 , N : 열 board = list() memo = [ [-1] * N for _ in range(M)] for _ in range(M) : line = list(map(int,sys.stdin.readline().split())) board.append(line) dirs = [ ..