본문 바로가기

728x90

알고리즘 문제 풀이/DFS,BFS24

[백준]7569번: 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 7576 토마토랑 같은 문제라서 어렵지 않게 문제를 맞추긴 했다. 다만 내가 리스트에 토마토 좌표정보를 x,y,z 순서가 아니라 z,x,y 순서로 저장해서 약간 헷갈릴 수 있고, 코드 가독성이 살짝 정신사나운 느낌 import sys from collections import deque input = sys.stdin.readline #n행 m열, 높이가 h m, n, h .. 2023. 2. 28.

[백준]9205번: 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 50m당 맥주 1병이 소진된다는 말은, 한 번에 최대 1000m까지 이동할 수 있다는 뜻이다. 이동 경로: 집 (-> 편의점1 -> 편의점2 -> .... -> 편의점n) -> 페스티벌 각각의 이동 거리가 1000보다 크지 않은 상태를 유지하며 도착지까지 도달하게 되면 happy를 출력하면 되는 문제이다. import sys from collections import deque input = sys.stdin.readline def dist(x1, y1, x2, y2): return abs(x1-x2) + abs(y1-y2) def bfs(x,y): q = deque() q.append((x,y)) visited=[] #방문한 편의점 좌표.. 2023. 2. 27.

[백준]11724번: 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 둘 다 해보니 bfs가 좀 더 빨랐다 1. 백준에서는 dfs하면 자꾸 RecursionError가 난다 -최대 재귀 깊이 설정값을 바꿔주면 되긴 하는데 이게 매번 해주기 좀 귀찮다 2. 그래프 요소 입력받을 때 input()으로 받으니 시간초과가 났다. -sys.stdin.readline()으로 받으면 해결됨 from collectio.. 2023. 2. 26.

[백준]7576번: 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 하다가 잘 안 돼서 다른 분들 코드 참고해서 수정했다.. 나는 언제쯤 혼자서 빠르게 풀 수 있을까?ㅠㅡㅠㅜ 아이디어 처음부터 익어 있는 토마토 좌표를 큐에 저장하고 bfs를 수행한다 인접한 칸 중에서 아직 안 익은 토마토가 있으면 (인접한 좌표의 그래프 값)을 (현재그래프값+1) 로 바꾸어준다 bfs가 종료되면 여전히 안 익은 토마토가 있는지 검사하고 결과를 출력한다. 익지 않은 .. 2023. 2. 25.

[백준]2468번: 안전 영역 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 방법: BFS 비는 높이 0부터 그 지역의 최고 높이까지 잠기게 할 수 있다. 0부터 최고높이까지 내렸을 때의 안전 영역 개수를 각각 구하여 리스트에 담은 후, 리스트의 최댓값을 출력했다. 0부터 최고 높이까지 안전 영역 개수 모두 구하기 maxH=max(map(max, graph)) #입력받은 지역의 최대 높이 result=[] for rain in range(maxH): visited = [[0.. 2023. 2. 25.

[백준]10026번: 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. 일반인 기준으로 bfs쫙 돌려서 구역이 몇 개인지 계산하여 출력한다. 2. 적록색약 기준으로 bfs를 다시 한 번 돌리기 위해 그래프를 살짝 변경해줬다. -그래프 모든 요소들을 비방문처리 -모든 G를 R로 바꿔줬다 (적록색약은 G와 R을 구별 못하니 하나로 통일시킴) 3. 적록색약 기준으로 bfs 한 번 더 돌려서 결과 출력 BFS로 연결요소 개수 구한 방식 -최초방문시에 bfs로 인.. 2023. 2. 24.

이전 1 2 3 4 다음

728x90

티스토리툴바