Algorithm/DFS&BFS (22) 썸네일형 리스트형 [Python] 백준 7576번 : 토마토 (S1) - DFS&BFS단계별6 #문제 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net #풀이 & 학습한 내용 "BFS로 토마토를 익히는 문제"입니다. bfs를 시작하기 전에 익은 토마토들을 먼저 모두 큐에 넣고 수행하는 것이 핵심입니다. 그리고 bfs가 끝나고 큐가 모두 비워지면 익을 수 있는 토마토는 모두 익은 것이므로, bfs이후에 안익은 토마토가 있는 지 확인하여 모두 익히는 것이 불가능한지 여부를 확인해주면 됩니다. #소스코드 from collections impo.. [Python] 백준 2178번 : 미로 탐색 (S1) - DFS&BFS단계별5 #문제 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #풀이 & 학습한 내용 "BFS의 특징은 각 정점을 최단경로로 방문한다는 것입니다. 이 점을 활용해 최단거리를 구해 보는 문제"입니다. 그저 평소의 bfs에서 최단경로를 세는 리스트만 추가해주면 해결되는 문제였습니다. 방문처리를 꼭 해주어 무한루프를 도는 일이 없게 해야 합니다. #소스코드(22번 쨰 줄 주목) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2.. [Python] 백준 1012번 : 유기농 배추 (S2) - DFS&BFS단계별4 #문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net #풀이 & 학습한 내용 "땅의 모습이 아니라 배추의 위치가 주어지는 문제"입니다. 땅에서 배추의 위치를 2차원 리스트에 넣고, 이를 그래프로 생각하여 DFS를 수행해 문제를 해결하였습니다. 첫 번째 제출에서 런타임 에러(RecursionError)가 발생하여 재귀 깊이를 연장해주어 제출했지만, PyPy3에서 메모리 초과가 발생하여 Python3로 제출하니 통과되었습니다. 앞으로 파이썬의 재귀 깊이가 기본적으로 최대 .. [Python] 백준 2667번 : 단지번호붙이기 (S1) - DFS&BFS단계별3 #문제 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net #풀이 & 학습한 내용 "2차원 배열을 그래프로 표현해 BFS나 DFS로 순회하는 문제"입니다. 2차원 배열을 그래프로 생각해서 DFS를 수행해 문제를 해결했습니다. 이때, 방향을 처음에 리스트로 설정해줘서 for문으로 편하게 접근할 수 있었습니다. BFS로 구현한다면, (x,y)인 튜플형태로 큐에 넣어줘야 할 것입니다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17.. [Python] 백준 2606번 : 바이러스 (S3) - DFS&BFS단계별2 #문제 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net #풀이 & 학습한 내용 "BFS나 DFS로 그래프를 순회해서 방문할 수 있는 정점을 찾는 문제"입니다. supremo7.tistory.com/174에서 구현한 DFS와 BFS코드를 조금만 변형하면 구현 가능했고, 이번 문제는 방문하지 않은 노드가 여러 개일 때, 꼭 번호가 낮은 순서부터 처리할 필요가 없어 아래 코드 35번째 줄 반복문에서 sort를 해주지 않았습니다. #소스코드 1 2 3 4 5 6 7 8 .. [Python] 백준 1260번 : DFS와 BFS (S2) - DFS&BFS단계별1 #문제 www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net #풀이 & 학습한 내용 "DFS와 BFS를 다루는 문제"입니다. DFS는 스택을 이용하는 알고리즘이며, 재귀 함수를 이용해서 간결하게 구현할 수 있습니다. 파이썬에서 스택을 이용할 때는 별도의 라이브러리를 사용할 필요 없이 기본 리스트에서 append()와 pop() 메서드를 이용하면 됩니다. 또한, BFS는 큐를 이용하는 알고리즘입니다. 파이썬에서 큐를 구현할 때는.. 이전 1 2 3 다음