본문 바로가기

PS/DFS_BFS14

[백준]4179번: 불! 파이썬 https://www.acmicpc.net/problem/4179 문제 설명미로 속에서 지훈이가 화재로부터 도망쳐야 한다. 미로의 크기와 구성은 주어지며, 지훈이는 미로의 가장자리로 탈출해야 한다. 불(F)은 매 초마다 확산되며, 지훈이는 불보다 먼저 가장자리에 도착해야 탈출할 수 있다.  풀이import sysfrom collections import dequedx = [1, 0, -1, 0]dy = [0, 1, 0, -1]def bfs(check): while q: x, y = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0  이 문제에서 유의할 점은 지훈이와 불이 동시에 움직인다는 것이다.그.. 2024. 6. 25.
[백준] 2667번: 단지번호붙이기 파이썬 https://www.acmicpc.net/problem/2667bfs로 탐색할때마다 갯수 세고, 집 수 세면 끝.import sysfrom collections import dequedef bfs(x,y): q = deque([(x,y)]) arr[x][y] = -1 house_count = 1 while q: x,y = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0  bfs문제는 많이 나오니까 관련 문제를 익숙해질때까지 많이 풀어야겠다. 2024. 6. 25.
[백준] 7569번: 토마토(3차원) 파이썬 https://www.acmicpc.net/problem/7569 유명한 토마토 문제근데 3차원인. 첫째 줄에 상자의 크기를 나타내는 M, N, H가 주어지고 각 줄마다 상자에 들어있는 토마토 상태가 주어짐:1: 익은 토마토0: 익지 않은 토마토-1: 토마토가 들어있지 않은 칸우리가 해야 할 일은 모든 토마토가 다 익을 때까지 며칠이 걸리는지 구하는 거임. 만약 처음부터 모든 토마토가 다 익어있으면 0을 출력하고, 토마토가 다 익지 못하면 -1을 출력하면 됨.   풀이 import sysfrom collections import deque# 방향 벡터 (상, 하, 좌, 우, 위, 아래)dx = [1, 0, -1, 0, 0, 0]dy =[0, 1, 0, -1, 0, 0]dz = [0, 0, 0, 0, 1,.. 2024. 6. 24.
[백준] 24483번, 24484번 : 알고리즘 수업 - 깊이 우선 탐색 5, 6 파이썬 https://www.acmicpc.net/problem/24483https://www.acmicpc.net/problem/2448424483번 풀이 (알고리즘 수업 - 깊이 우선 탐색 5)알고리즘 수업 - 깊이 우선 탐색 1, 3(24479번, 24481번) 두 문제에서 출력하는 값을 그냥 곱해서 합한후 출력하기만 하면된다. 24483번 코드import syssys.setrecursionlimit(10**9)def dfs(r, d): global cnt visited[r] = cnt depth[r] = d line[r].sort() #오름차순으로 정렬 for i in line[r]: if visited[i] == 0: cnt+=1 dfs(i, d +1)n,m,r =map.. 2024. 6. 22.

티스토리툴바