[Coding Test]

[백준] 24479 파이썬(python) : 알고리즘 수업 - 깊이 우선 탐색 1

24479번 : 알고리즘 수업 - 깊이 우선 탐색 1 pypy3로 제출하면 메모리초과가 발생하니 python3로 제출해야한다. import sys sys.setrecursionlimit(10**9) #1 n, m, r = map(int, sys.stdin.readline().split()) graph = [ [] for _ in range(n+1) ] #2 visit = [0] * (n + 1) #3 for _ in range(m): a, b = map(int, sys.stdin.readline().split()) #4 graph[a].append(b) #5 graph[b].append(a) count = 1 def dfs(v): global count visit[v] = count #7 graph[v]..

[백준] 1260 파이썬(python) : DFS와 BFS - (다른풀이)

1260번 : DFS와 BFS 다른 사람의 풀이) from collections import deque n, m, v = map(int, input().split()) vertex = [ [0]*(n+1) for i in range(n+1) ] #6 for i in range(m): a, b = map(int, input().split()) vertex[a][b] = vertex[b][a] = 1 #1 visit = [0] * (n+1) def dfs(v): visit[v] = 1 #2 print(v, end=" ") for i in range(1, n+1): if visit[i] == 0 and vertex[v][i]==1: dfs(i) #3 def bfs(v): visit[v] = 0 #4 q = d..

[백준] 1182 파이썬(python) : 부분수열의 합 - (조합)

1182번: 부분수열의 합  def dfs(idx, sum): global answer if(idx >= n): #1 return sum += arr[idx] #2 if s == sum: #3 answer += 1 dfs(idx+1, sum-arr[idx]) #4 dfs(idx+1, sum) #5n, s = map(int, input().split())arr = list(map(int, input().split()))answer = 0dfs(0, 0)print(answer) #1 : 재귀함수 탈출조건(idx가 깊이이고 배열의 idx는 n-1까지 이므로 idx == n이면 탈출)#2 : 자신의 위치의 값 포함#3 : 만들 수 있으면 answer +1..

[백준] 14502 파이썬(python) : 연구소 - (★)

14502번 : 연구소 빈칸에 벽을 3개 세워서 바이러스를 퍼지게 한 다음 가장 많은 빈칸이 남도록 해야한다. 1) 빈칸을 돌며 벽 3개를 세운다 -> n, m의 최댓값은 8이기 때문에 완전탐색으로 모든경우를 돌 수 있다. 그리고 벽 3개를 세워 나머지는 배제해야 하기에 백트래킹을 떠올린다. 2) 벽을 모두 세운 후 그 경우에 대해 바이러스를 전파시키는데 연결되어 있는 바로 이웃칸으로 전염될 수 있으니까 bfs를 사용한다. 다 전염시키고 나서 빈칸(0)의 개수를 센다. ==> 백트래킹 안에서 bfs를 호출한다. from collections import deque visit = [[0 for col in range(10)] for row in range(10) ] #1 dx = [ 0, 0, 1, -1 ..

[백준] 2206 파이썬(python) : 벽 부수고 이동하기 - (3중 리스트)

2206번 : 벽 부수고 이동하기 전 포스팅에서 풀었던 bfs문제(2178번 미로탐색)에 조건을 하나 더 추가한 문제이다. 지금의 나로선 새로운 조건을 추가한것을 구현하는데 상당히 어렵고 답을 이해하는것도 힘들었다. 더 정진하겠다. import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) graph = [ list(map(int, sys.stdin.readline().strip())) for _ in range(n) ] #1 visited = [[ [0, 0] for _ in range(m) ] for _ in range(n) ] #2 visited[0][0][0] = 1 #3 dx = [ 0, 0, -1,..

[백준] 2178 파이썬(python) : 미로 탐색

2178번 : 미로 탐색 그래프이론 문제 중에서도 너비 우선 탐색을 하는 bfs문제다. 파이썬에서는 deque라이브러리를 import해와서 사용한다. 너비 우선 탐색에 대해서는 조만간 포스팅 해보겠다. 첫번째 풀이) from collections import deque n, m = map(int, input().split()) graph = [ list(map(int, input())) for _ in range(n) ] #1 d = [ (-1, 0), (1, 0), (0, -1), (0, 1) ] #2 q = deque() #3 q.append((0,0)) #4 def bfs(): while q: #5 x, y = q.popleft() #6 for i in range(4): #7 dx = x + d[i..