본문 바로가기

Python/DFS&BFS22

99클럽 코테 스터디 10일차 TIL + 백준 2573 빙산 (파이썬) ※ 2573 빙산https://www.acmicpc.net/problem/2573문제 해결 TIP기존 bfs 알고리즘으로 탐색과 녹이기를 동시에 수행할 수 있다.  전체 코드 from collections import dequeimport sysinput = sys.stdin.readlinedx = [-1,0,1,0]dy = [0,1,0,-1]N, M = map(int,input().split())graph = []year = 0for i in range(N): graph.append(list(map(int,input().split())))def bfs(x,y): queue = deque() queue.append((x,y)) visited[x][y] = 1 while queu.. 2025. 1. 25.
99클럽 코테 스터디 9일차 TIL + 백준 1707 이분 그래프 (파이썬) ※ 1707 이분 그래프https://www.acmicpc.net/problem/1707문제 해결 TIP문제를 먼저 이해해보자.이분 그래프란 아래 그림과 같이, 이웃하는 정점끼리 가지는 색깔이 달라야 하는 것이다.bfs로 구현하여 주변 정점들을 탐색하면서 색칠해주고, 만약 색깔이 다르다면 이분 그래프가 아니다라는 판단을 내릴 수 있다. 전체 코드from collections import dequeimport sysinput = sys.stdin.readlineK = int(input())for i in range(K): V, E = map(int,input().split()) graph = [[] for _ in range(V+1)] color = [0]*(V+1) for j in .. 2025. 1. 23.
99클럽 코테 스터디 8일차 TIL + 백준 2667 단지번호붙이기 (파이썬) ※ 2667 단지번호붙이기https://www.acmicpc.net/problem/2667문제 해결 TIP해당 문제는 dfs로도, bfs로도 풀 수 있다.  전체 코드 dfs로 풀기N = int(input())graph = []for i in range(N): graph.append(list(map(int,input())))def dfs(x,y): if x=N or y=N: return False if graph[x][y] == 1: graph[x][y] = result+2 dfs(x-1,y) dfs(x,y-1) dfs(x+1,y) dfs(x,y+1) return True return Falser.. 2025. 1. 22.
99클럽 코테 스터디 7일차 TIL + 백준 1697 숨바꼭질 (파이썬) ※ 1697 숨바꼭질https://www.acmicpc.net/problem/1697문제 해결 TIP문제에 주어진 대로 x - 1, x + 1, x * 2 총 3가지 방법이 있다. 동생의 점 K와 같을 때까지 반복하며, 시간은 dist 배열을 통해 1씩 추가해주며 구한다. 전체 코드from collections import dequeN, K = map(int,input().split())def bfs(): queue = deque() queue.append(N) while queue: x = queue.popleft() if x == K: print(dist[x]) break for i in (x - 1, x +.. 2025. 1. 21.
99클럽 코테 스터디 6일차 TIL + 백준 1260 DFS와 BFS (파이썬) ※ 1260 DFS와 BFShttps://www.acmicpc.net/problem/1260문제 해결 TIPDFS는 스택으로, BFS는 큐로 구현한다. 문제 해결 풀이그래프 리스트에 각 노드가 연결된 정보를 표현한다. 전체 코드from collections import dequeN, M, V = map(int,input().split())graph=[[] for _ in range(N+1)]for i in range(M): num1,num2 = map(int,input().split()) graph[num1].append(num2) graph[num2].append(num1)graph = [sorted(g) for g in graph]visited = [False]*(N+1)graph2 .. 2025. 1. 21.
[Algorithm] 백준 1261 알고스팟 | 파이썬 BFS ※ 1261 알고스팟https://www.acmicpc.net/problem/1261 문제 해결 TIP이전 미로만들기와 동일한 문제이다. n, m 값의 범위만 재설정해준다. 전체 코드from collections import dequedx = [0,0,-1,1]dy = [-1,1,0,0]def bfs(x,y): queue = deque() queue.append((x,y)) visited = [[-1] * m for _ in range(n)] visited[x][y] = 0 while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + .. 2024. 9. 11.
[Algorithm] 백준 2665 미로만들기 | 파이썬 BFS ※ 2665 미로만들기https://www.acmicpc.net/problem/2665 문제 해결 TIPvisited 배열에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 저장한다. bfs로 탐색하면서, 흰 방인 경우를 먼저 탐색한다.(appendleft) 검은 방일 경우에는 이전 visited값에 1을 추가해준다. 전체 코드from collections import dequedx = [0,0,-1,1]dy = [-1,1,0,0]def bfs(x,y): queue = deque() queue.append((x,y)) visited = [[-1] * n for _ in range(n)] visited[x][y] = 0 while queue: x, y = queue.p.. 2024. 9. 11.
[Algorithm] 백준 7562 나이트의 이동 | 파이썬 BFS ※ 7562 나이트의 이동https://www.acmicpc.net/problem/7562 문제 해결 TIPbfs로 간단하게 풀 수 있다. 기존의 문제들은 상하좌우로 움직일 수 있지만 이 문제는 대각선으로 8방향 이동할 수 있다. 이에 맞춰서 dx, dy를 재설정해준다. 이후 최단거리 문제와 비슷하게 1씩 추가해가며 이동량을 그래프에 저장한다. 목표 좌표에 도달하면 이동량을 출력한다. 전체 코드from collections import dequen = int(input())for i in range(n): l = int(input()) graph = [[0]*l for _ in range(l)] i, j = map(int,input().split()) r, c = map(int,in.. 2024. 7. 22.
[Algorithm] 백준 1926 그림 | 파이썬 BFS ※ 1926 그림https://www.acmicpc.net/problem/1926 문제 해결 TIPbfs로 간단하게 풀 수 있다. 유기농 배추 문제와 비슷하다. 전체 코드from collections import dequegraph = []n, m = map(int,input().split())for i in range(n): graph.append(list(map(int,input().split())))#graph = [[1, 1, 0, 1, 1], [0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [1, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1]]dx = [-1,1,0,0]dy = [0,0,-1,1]def bfs(x,y): graph[x][.. 2024. 7. 16.

티스토리툴바