문제 설명 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀이 전형적인 BFS 문제 시작점이 여러 개인 BFS 문제를 처음 풀어봐서 풀다가 당황 ,,,, BFS 자체가 너비 우선으로 탐색하기 때문에 1일차, 2일차 이렇게 순서대로 큐에 들어간다 처음 시작점을 찾은 후 큐에 넣은 다음 BFS를 수행하면 된다 ! 다 풀고 나서 코드 리뷰를 해본 결과 bfs 함수 안에서 큐를 다 돌고 나서 안 익은 토마토가 있을 때(값이 0일..
bfs
문제 설명 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제 풀이 visited로 방문 여부를 기록하였고, 이중 포문으로 값이 1이면서 아직 방문하지 않은 지점일 때 bfs를 시작하여 bfs의 시작점을 구했다. 가장 넓은 그림의 넓이를 출력하기 위해 max를 사용하여 비교했다! from collections import deque n, m = map(int, input().split()) visited = [[False] * m for _ in ..
문제 설명 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 가장 기본적인 BFS 문제 경로의 최단 거리를 구하는 문제이기 때문에 BFS로 풀었다 만약 경로가 몇 가지인지를 묻는다면 DFS로..! 미로 범위에서 벗어난 경우이거나, 이동할 수 없는 칸을 무시하고 해당 칸을 처음 방문했을 때 이전 지점까지의 최단거리 + 1 해주었다 from collections import deque def bfs(x, y): queue = deque() queue.append((x, ..
대표 문제 유형 경로 탐색 (최단 거리, 시간) 최단 거리 : BFS 경로의 가짓수(경우의 수) : DFS 네트워크 (연결) 조합 (모든 조합 만들기) 구현 방법 DFS : Stack, 재귀함수 BFS : Queue, LinkedList 무방향 그래프 # 각 노드가 연결된 정보를 표현 (2차원 리스트) # 보통 문제에서 1부터 시작하기 때문에 인덱스 0은 비워둠 graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 표현 (1차원 리스트) visited = [False] * 9 DFS (Depth First Search) DFS를 설명할 때는 보통 ‘번호가 낮은 인접 노드부터 방문..
