본문 바로가기

BFS12

[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.
[Algorithm] 백준 16234 인구 이동 | 파이썬 BFS ※ 16234 인구 이동https://www.acmicpc.net/problem/16234문제 해결 TIP모든 나라의 위치에서 BFS를 수행하여 인접한 나라의 인구수를 확인한 뒤에, 가능하다면 국경선을 열고 인구 이동 처리를 진행한다. visited 배열을 따로 두어 index를 확인하면서 더 이상 인구 이동을 할 수 없을 때까지 반복한다. BFS를 처리할 때 인구 분배를 같이 해나가는게 중요한 것 같다.   전체 코드 from collections import dequeN, L, R = map(int,input().split())graph = []for i in range(N): graph.append(list(map(int,input().split())))#graph = [[50, 30], [2.. 2024. 7. 3.
[Algorithm] 백준 18405 경쟁적 전염 | 파이썬 BFS ※ 18405 경쟁적 전염https://www.acmicpc.net/problem/18405첫번째 문제 풀이 (시간 초과)문제를 보고 먼저 생각해낸 해결방법은1. 바이러스 번호 1번부터 graph에서 위치한 자리값을 position 배열에 저장한다.2. position 배열에서 하나씩 꺼내어 확산을 진행한다.N, K = map(int,input().split())graph = []for i in range(N): graph.append(list(map(int,input().split())))S, X, Y = map(int,input().split())#graph = [[1, 0, 2], [0, 0, 0], [3, 0, 0]]dx = [-1,1,0,0]dy = [0,0,-1,1]def bfs(x,y,.. 2024. 7. 2.
[Algorithm] 백준 10026 적록색약 | 파이썬 BFS ※ 10026 적록색약https://www.acmicpc.net/problem/10026문제 해결 TIP유기농 배추 문제와 같이 처음에 DFS로 풀다가 RecursionError에 걸려서 BFS로 바꾸었다. 적록색약인 것과 아닌 것의 그래프를 애초에 따로 저장하여 bfs로 돌려주었다. 전체 코드from collections import dequedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]N = int(input())graph = [] #적록색약이 아닌 그래프for i in range(N): graph.append(list(map(str,input())))new_graph = [row[:] for row in graph] #적록색약이 보는 그래프# 새로운 그래프에서 'G' 값을.. 2024. 6. 29.
[Algorithm] 백준 7576 토마토 | 파이썬 BFS ※ 7576 토마토https://www.acmicpc.net/problem/7576문제 해결 TIP이코테의 미로 탈출과 비슷한 문제라고 생각했다. BFS를 이용하여 토마토를 전염시킨 후 최단 거리를 반환하는 것과 같이 전염하면서 이전 값에 1을 추가하여 값을 저장하도록 한다. 이때 주의할 점은 2차원 배열의 첫번째 원소부터 탐색 시작하는 것이 아닌, 1을 가진 토마토라면 동시에 전염이 시작되어야 한다는 것이다. 최종적으로 바뀐 2차원 배열 graph에 익지 않은 토마토가 있다면 -1을 반환하고 그렇지 않으면 최소 일수(graph에서 가장 큰 원소값-1)를 반환한다. 이때 이미 처음부터 모든 토마토가 익어있는 상태라면 0을 출력하게 되어있는데, 어차피 graph에서 가장 큰 원소값이 1일테니 0을 반환할 .. 2024. 6. 27.
[Algorithm] 백준 1012 유기농 배추 | 파이썬 BFS ※ 1012 유기농 배추https://www.acmicpc.net/problem/1012문제 해결 TIP처음에 DFS로 풀다가 RecursionError에 걸려서 BFS로 바꾸었다. 바이러스 문제와 비슷하게 상하좌우 주변 노드들을 방문하며 큐에 삽입하고 탐색하는 방법으로 진행한다. 여기서 주의할 점은 문제에서 가로 길이를 M, 세로 길이를 N으로 주어진 점이다. 전체 코드from collections import dequedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]def bfs(x, y): queue = deque() queue.append((x, y)) while queue: x, y = queue.popleft() for i in rang.. 2024. 6. 26.

티스토리툴바