[백준 / 파이썬] 2573 빙산

BFS 함수를 2개만들었다. 1. 1년마다 녹는걸 구현하는 BFS 2. 그 후에 몇덩이로 나눠졌는지 확인하는 BFS를 구현했다. 까다로웠던 부분은 첫번째 BFS에서 바다인 부분은 방문처리를 하면 안된다는 부분이다. 왜냐면 빙산은 상하좌우 빙하의 개수에 의해 깎여나가는데 바다를 방문처리해서 들리지 않게 된다면 깎이는 부분이 적어지기 때문이다. from collections import deque n, m = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] time = 0 def bfs(a, b): global time visited =..

• format_list_bulleted Algorithm
• · 2023. 2. 5.
• textsms

[백준] Python 2667 단지번호붙이기 DFS/BFS

모든 행, 열을 완전탐색하여 1인곳을 찾아 DFS 혹은 BFS로 들어가면된다. BFS 좀 해메었지만 원리는 단순하다. 방문처리가 필요없이 방문한 곳들을 0으로 만들어 주고 cnt를 늘리는 방식으로 단지가 몇개인지 세면된다. from collections import deque n = int(input()) graph = [list(map(int, input())) for _ in range(n)] # 모든 인덱스를 확인하여 1이 있으면 bfs로 지난부분 0으로 만들기., 다 파고들면 다시 방문안한 1부터 dfs house = [] dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] def bfs(r, c): q = deque() q.append((r, c)) graph[r][c] = 0 ..

• format_list_bulleted Algorithm
• · 2023. 2. 4.
• textsms

[백준] Python 2606 바이러스 BFS/DFS로 풀이.

먼저 DFS 풀이. 방문한 노드면 재귀 종료. 방문 안한 노드면 방문처리 해주고 연결된 노드들 확인. from collections import defaultdict n = int(input()) connect_len = int(input()) dic = defaultdict(list) for i in range(connect_len): a, b = map(int, input().split()) dic[a].append(b) dic[b].append(a) # 양방향 # dfs 접근 visited = [False for _ in range(n+1)] # 1번부터 시작하기 위해 n+1 def dfs(v, visited): global cnt if visited[v]: return visited[v] = Tr..

• format_list_bulleted Algorithm
• · 2023. 2. 4.
• textsms

[프로그래머스] BFS / 게임 맵 최단거리

queue 를 이용한 BFS 문제이다. 자세한 설명은 주석을 통해.. from collections import deque def solution(maps): row = len(maps) col = len(maps[0]) dx = [-1, 1, 0, 0] # col 증가는 오른쪽으로 증가 dy = [0, 0, -1, 1] # row 증가는 아래쪽으로 증가 graph = [[-1 for _ in range(col)] for _ in range(row)] # 이동 칸 수를 기록하기 위한 그래프 q = deque() q.append([0,0]) # 시작위치 graph[0][0] = 1 # 시작점은 그자체로 1칸 이동한 것으로 침. while q: y, x = q.popleft() # 행, 열로 탐색할 것이기 ..

• format_list_bulleted Algorithm
• · 2023. 1. 21.
• textsms