전체 글

[백준1707&파이썬] BFS를 활용하여 이분 그래프를 판별하는 방법

# 문제 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net # 코드 import sys from collections import defaultdict from collections import deque RED = 1 BLUE = -1 def solve(): V, E = map(int, sys.stdin.readline().split()) # V 정점의 개수, E 간선의 개수 graph = defaultdict(list) visit = [0] * (V + 1) # 0 == 방문X , 1 == RED , -1 ..

[백준2251&파이썬] BFS는 가지치기로 경우의 수를 구하기 적합하며 방문처리의 방법을 생각해보자

# 문제 백준 2251 물통 파이썬 풀이 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net # 코드 import copy import sys from collections import deque A, B, C = map(int, sys.stdin.readline().split()) max_size = (A, B, C) result = set() # visit를 어떻게 처리할 것인가 ? ## 병이 똑같은 상태가 된다면 visit로 처리하는게 맞을듯 하다. ## 3차원 배열을 쓰는건 너무 메모리..

[백준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..