그래프
[백준/BOJ]#13565:침투[DFS/그래프/깊이우선탐색/파이썬/python]
https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 메모리 초과의 늪에서 못 빠져나오게 한 문제,,, 대체 코드에 문제가 없는데 왜 이러는건가 재귀탐색제한을 줄여도 보고 30분을 헤매었는데,, 결국 컴파일러를 pypy3가 아닌 python3 으로 바꾸니 통과했다;;; 백준에서 이런 경우가 간혹 있는데 이럴때마다 시간이 아깝고 힘 빠진다^^;; 승부는 내야하니 정답은 내야겠고,, bfs보다는 dfs로 푸는 게 더 ..
[백준/알고리즘] #16953: A → B [파이썬(python)/그래프/DFS]
https://www.acmicpc.net/problem/16953 #16953_A->B from collections import deque A, B= map(int, input().split()) def dfs(x,y): q=deque([(x,y)]) while q: num, cnt = q.popleft() if num == B: return cnt if num * 2
[백준/알고리즘] #2178: 미로탐색 [파이썬(python)/그래프/BFS]
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #2178_미로탐색 from collections import deque N, M = map(int, input().split()) maze = [] for _ in range(N): maze.append(list(map(int, input()))) def bfs(x,y): dx=[-1,1,0,0] dy=[0,0,-1,1] q=deque() q.append((x,y)) while q: x,y=q.popleft() for i in..
[백준/알고리즘] #2583: 영역 구하기 [파이썬(python)/그래프/DFS/BFS]
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net #2583_영역 구하기 import sys from collections import deque input = sys.stdin.readline M, N, K = map(int, input().split()) #M:세로, N:가로 (상하반전) dy = [-1,1,0,0] dx = [0,0,-1,1] graph = [list([0]*N) for _ in range(M)] def ..
[백준/BOJ/알고리즘/파이썬(python)]#11725_트리의 부모 찾기[트리/그래프]
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 루트 1부터 시작해서 dfs로 탐색하는 알고리즘으로 풀었다. 방문유무 정보 저장하는 배열을 하나 만들고 방문하지 않았다면 부모노드를 업뎃하면서 dfs탐색하면 된다. 재귀로 한 번 풀고 큐로 한 번 풀었다. 파이썬 코드_재귀 풀이(recursion) #11725_recursion import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) N = int(input()) tree = [[] for _ in..
[백준/boj/알고리즘/파이썬(python)/C++/DFS]#11724:연결요소의 개수
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 그래프이론_너비우선탐색, 깊이우선탐색 BFS DFS 문제 나는 DFS를 이용하여 풀었다. (BFS까지 나중에 풀어봐야지!) 파이썬 코드에서 계속 시간초과가 나서 그 원인을 보니 input() 이었다. 백준에서는 input()함수가 시간초과가 잘 난다고 하니 참고하시길..! sys 라이브러리 import해서 입출력하면 해결된다. 그리고 ..