[백준] 7576번 - 토마토 풀이 시간: 40분 이내 1) 문제 해결 아이디어 토마토가 모두 익을 때까지 최소 날짜를 구하는 문제다. 익은 토마토가 상하좌우로 인접한 위치에 있는 익지 않은 토마토를 익힌다. 지금껏 풀어왔던 최단 경로 문제와 비슷하며 이 문제는 BFS로 풀어야 한다. 이 문제에서 3가지 케이스가 있다. 1. 저장될 때부터 모든 토마토가 익어있는 경우(즉, 입력받은 2차원 리스트에 0인 값이 없다면) -> 0 출력 2. 토마토가 익는 과정이 모두 끝난 후 토마토가 모두 익지 못하는 경우(즉, bfs 수행 후 2차원 리스트에 0인 값이 하나라도 있으면) -> -1 출력 3. 토마토가 익는 과정이 모두 끝난 후 토마토가 모두 익었을 경우(즉, bfs 수행 후 2차원 리스트에 0인 값이 하나도..
[백준] 2667번 - 단지번호붙이기 풀이 시간: 30분 이내 이 문제는 DFS, BFS 2가지 방법으로 모두 풀 수 있는 문제다. BFS보다 DFS로 해결하는 것이 메모리, 시간 측면에서 더 효율적이었다. 동작 과정의 3~4는 DFS, BFS 풀이 둘 다 동일하다. (풀이1) BFS 1) 문제 해결 아이디어 1. 현재 좌표 삽입, 방문처리 2. 상하좌우 탐색 2-1. 좌표 꺼내기, 집 수(num) 1증가 2-2. 해당 좌표 기준 인접 좌표가 정상 범위 내이고 집이면 삽입, 방문처리 3. 해당 그래프의 모든 좌표수(num) 리스트(house)에 삽입 4. 지도 좌표가 1일 때마다 위 과정을 반복 좌표를 꺼낼 때(popleft() 할 때) 집 수를 센다! 2) 소스코드 from collections imp..
[백준] 1260번 - DFS와 BFS 풀이 시간: 35분 이내 1) 문제 해결 아이디어 그래프를 DFS, BFS로 탐색한 결과를 출력하는 문제였다. DFS는 재귀함수로 BFS는 큐(deque)로 구현하였다. 인접 노드 방문 조건: 정점 번호가 작은 순서 여기서는 방문할 수 있는 인접 노드가 여러 개인 경우에 정점 번호가 작은 것을 먼저 방문하는 조건이 있기 때문에 각 정점별 인접 노드 번호를 오름차순으로 정렬해주어야한다. 개인적으로 반복문을 이용하여 구현하는 BFS보다 재귀함수를 이용해야하는 DFS가 조금 더 익숙치 않아 어려운 것 같다. 현재 노드를 방문처리하고 인접 노드를 검사하는 것까지는 동일하지만 DFS에서는 인접 노드가 방문되지 않은 노드라면 해당 노드를 재귀호출하고 BFS에서는 인접 노드가 ..
