BFS_시작점이 여러개 (파이썬)
2022. 9. 10. 17:13
알고리즘 개념
BFS_시작점이 여러개 시작점이 여러개인 BFS 시작점이 여러개인 BFS탐색의 대표적으로 가스가 퍼지는 상황이 있다. 이 경우, 배열에 대해 완전 탐색을 하고, visited에 넣어 주는 값을 조금만 바꿔 주면 된다. 코드 def bfs(N, M): # 여러개의 시작점을 갖는 bfs, 시작점에서의 거리를 탐색하며 알아냄 for i in range(N): for j in range(M): if tomato[i][j] == 1: Q.append((i, j)) while Q: i, j = Q.popleft() for di, dj in [[0, 1], [1, 0], [-1, 0], [0, -1]]: nr, nc = i + di, j + dj if 0
백준 7576 토마토 BFS (파이썬)
2022. 9. 10. 17:02
백준
아이디어 시작점이 여러개인 bfs탐색을 활용해야겠다. (독가스가 퍼지는 상황과 비슷하다.) visited에 시작점으로 부터의 거리를 넣어놓자. 풀이 import sys from collections import deque def bfs(N, M): # 여러개의 시작점을 갖는 bfs, 시작점에서의 거리를 탐색하며 알아냄 for i in range(N): for j in range(M): if tomato[i][j] == 1: Q.append((i, j)) while Q: i, j = Q.popleft() for di, dj in [[0, 1], [1, 0], [-1, 0], [0, -1]]: nr, nc = i + di, j + dj if 0
백준 1012 유기농 배추 DFS (파이썬)
2022. 9. 5. 19:54
백준
아이디어 이거 전에 풀어봤던 단지번호붙이기랑 똑같다. 그거 보다 쉽다. 영역의 갯수만 알아내면 되기 때문. 2667_단지번호붙이기 dfs사용하자. 풀이 및 해설(주석) import sys sys.setrecursionlimit(10 ** 6) # 일단 혹시 몰라 넣어줌 def dfs(N, M, r, c): # 미로에서 dfs를 사용하는 것과 같이 재귀 dfs를 선언 visited[r][c] = 1 for dr, dc in [[0, 1], [1, 0], [0, -1], [-1, 0]]: nr, nc = r + dr, c + dc if 0
Queue 큐 (파이썬)
2022. 9. 3. 21:18
알고리즘 개념
Queue Queue란? Queue는 기본적으로 stack과 동일하게 자료를 삽입, 삭제할 수 있는 자료 구조이다. 다른 점은 Queue에 삽입한 순서대로 원소가 저장되고, 가장 먼저 삽입한 원소는 가장 먼저 삭제가 된다. (선입 선출) Queue의 자료 인덱스를 가리키는 두 가지 변수가 존재한다. 머리(front)와 꼬리(rear)로 통상 지칭한다. Stack과 마찬가지로 원소를 삽입, 삭제할 때 Queue가 꽉찼는지, 비었는지 확인해야한다. 삽입과 삭제는 다음과 같이 이루어 진다. 초기 상태는 front = rear = -1이다. 생각해볼 점 Queue를 사용할 때 front와 rear를 두지 않고 append와 pop(0)을 이용하여 Queue를 사용할 수도 있다. 하지만 이런 경우, 삽입과 삭제가..
백준 10026 적록색약 sys.setrecursionlimit (파이썬)
2022. 9. 3. 18:47
백준
아이디어 DFS를 미로찾기 형식으로 활용해서 구역 나누면 되겠다. 적록색약이 볼 때는 R과 B가 같으니 B를 R로 바꾸고 1의 작업을 다시 하면되겠다. 풀이 및 코드(해설) import sys sys.setrecursionlimit(10 ** 6) # 핵심!!!!!!!!!!! di = [0, 1, 0, -1] dj = [1, 0, -1, 0] def dfs(color, N, r, c): visited[r][c] = 1 for dr, dc in [[0, 1], [1, 0], [0, -1], [-1, 0]]: nr, nc = r + dr, c + dc if 0
백준 2667 단지번호붙이기 (파이썬)
2022. 9. 3. 18:14
백준
아이디어 BFS보다는 DFS탐색이 좋을 것 같다. DFS를 재귀함수로 만들고 함수가 실행된 횟수가 아파트의 수다. 한번 코드를 작성해보자 풀이 및 해설(주석) import sys def dfs(N, r, c): # dfs탐색 visited[r][c] = 1 # 일단, visited에 방문 표시 global total total += 1 # dfs가 실행 된다는 것은 주변에 아파트가 있다는 것, 아파트 수를 더해줌 for dr, dc in [[0, 1], [1, 0], [0, -1], [-1, 0]]: # 상,하,좌,우로 델타주기 nr, nc = r + dr, c + dc if 0
백준 2606 바이러스 (파이썬)
2022. 9. 3. 18:11
백준
아이디어 BFS를 활용해서 visited에 다녀간 것만 더해주면 된다. 풀이 및 해설(주석) from collections import deque import sys def bfs(v): # bfs 반복 코드 Q.append(v) # 일단, 시작점을 Q에 넣어준다. D[v] = 0 # D는 시작점 부터의 거리 visited[v] = 1 # visited 방문 해주고 while Q: # Q가 빈 리스트가 될 때 까지 v = Q.popleft() # Q의 제일 앞인덱스를 뽑아준다. for w in G[v]: # 노드가 갈 수 있는 곳 if not visited[w]: # 방문하지 않았다면 Q.append(w) # 그 노드를 Q에 append visited[w] = 1 # visited 방문하고 D[w] = ..
DFS (깊이 우선 탐색) (파이썬)
2022. 9. 3. 18:08
알고리즘 개념
DFS (깊이 우선 탐색) DFS란? 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길의 갈 수 있는 경로로 다시 탐색하는 방법 가장 마지막에 만났던 갈림길의 정점으로 되돌아가야해서 후입선출 구조의 stack사용 DFS코드 (재귀) 나는 계속 재귀를 통한 DFS함수를 작성하고 사용해서 재귀만 쓰겠음. def dfs(v): # 함수에서 자체적으로 내부에 stack이 쌓이므로 따로 stack을 사용하지는 않음. visited[v] = 1 # visited에 방문 처리 for w in G[v]: # 간선의 정보를 담은 G리스트를 순회 if visited[w] == 0: # 방문 안했다면, dfs(w) # dfs 재귀s(w) 보면, 코..