[백준] 7569번 - 토마토 풀이 시간: 1시간 이내 1) 문제 해결 아이디어 이전 문제(7576번)과 거의 동일한 문제로 이 문제도 BFS를 이용하여 답을 도출해 낼 수 있다. 로직 자체는 똑같기 때문에 3차원 리스트로 입력받고 잘 처리하기만 하면 쉽게 풀 수 있는 문제였다. 하지만 3차원 리스트를 입력받고 다루는데 익숙치 않아 조금 시간이 걸렸던 것 같다. 7576번 7579번 1 graph: 2차원 리스트 graph: 3차원 리스트 2 탐색 방향: 상하좌우(4개) 탐색 방향: 위, 아래, 왼쪽, 오른쪽, 앞, 뒤(6개) 2) 소스코드 from collections import deque # 가로, 세로, 높이 m, n, h = map(int, input().split()) # 0: 안익음, 1: ..
[백준] 7576번 - 토마토 풀이 시간: 40분 이내 1) 문제 해결 아이디어 토마토가 모두 익을 때까지 최소 날짜를 구하는 문제다. 익은 토마토가 상하좌우로 인접한 위치에 있는 익지 않은 토마토를 익힌다. 지금껏 풀어왔던 최단 경로 문제와 비슷하며 이 문제는 BFS로 풀어야 한다. 이 문제에서 3가지 케이스가 있다. 1. 저장될 때부터 모든 토마토가 익어있는 경우(즉, 입력받은 2차원 리스트에 0인 값이 없다면) -> 0 출력 2. 토마토가 익는 과정이 모두 끝난 후 토마토가 모두 익지 못하는 경우(즉, bfs 수행 후 2차원 리스트에 0인 값이 하나라도 있으면) -> -1 출력 3. 토마토가 익는 과정이 모두 끝난 후 토마토가 모두 익었을 경우(즉, bfs 수행 후 2차원 리스트에 0인 값이 하나도..
[백준] 2178번 - 미로 탐색 풀이 시간: 30~40분 이내 1) 문제 해결 아이디어 이 문제는 시작 위치(1, 1)에서 도착 위치(N, M)으로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제다. 즉, 최단 경로를 구하는 문제로 BFS로 풀 수 있는 대표적인 문제이다. BFS로 문제를 풀어야 한다는 것은 알았으나 방문 처리를 할 때 기록해야하는 값을 전역변수로 변경, 대입하여 약간의 어려움을 겪었다. 첫번째 오류. 최소 이동 칸 수를 구하기 위해 전역변수를 쓴 것 처음에 이동 칸 수를 나타낼 전역변수(res)를 선언하고 popleft()할 때마다 res 값을 1 증가했다. 상하좌우를 탐색할 때 갈 수 있는 칸이면 큐에 삽입하고 방문처리를 하는데 칸의 값을 res를 넣어주려고 했다. 그리고 마지막..
[백준] 1012번 - 유기농 배추 풀이 시간: 30분 이내 이 문제는 DFS, BFS 2가지 방식으로 모두 풀 수 있는 문제다. 최대 재귀한도 깊이 문제로 BFS로 풀이하는 것이 더 좋을 듯 하다. (풀이1) BFS 1) 문제 해결 아이디어 2) 소스코드 from collections import deque # 위치벡터(상하좌우) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # BFS def bfs(x, y): # 시작 좌표 삽입, 방문처리 queue = deque() queue.append((x, y)) graph[x][y] = 0 while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[..
[백준] 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..
[백준] 2606번 - 바이러스 풀이 시간: 10분 이내 (풀이1) BFS 이용 이 문제는 노드 1이 포함된 그래프에서 1을 제외한 노드의 수를 구하는 문제다. 해당 문제는 입력받은 간선 정보를 통해 그래프(2차원 리스트)를 만들고 DFS/BFS로 문제를 풀 수 있다. 1) 문제 해결 아이디어 아래 코드는 BFS로 구현한 방법이다. 2) 소스코드 from collections import deque n = int(input()) # 컴퓨터 수 m = int(input()) # 컴퓨터 간선 수 graph = [[] for _ in range(n + 1)] visited = [False] * (n + 1) res = 0 # 1이 감염시킨 컴퓨터 수 for i in range(m): a, b = map(int..
[백준] 1260번 - DFS와 BFS 풀이 시간: 35분 이내 1) 문제 해결 아이디어 그래프를 DFS, BFS로 탐색한 결과를 출력하는 문제였다. DFS는 재귀함수로 BFS는 큐(deque)로 구현하였다. 인접 노드 방문 조건: 정점 번호가 작은 순서 여기서는 방문할 수 있는 인접 노드가 여러 개인 경우에 정점 번호가 작은 것을 먼저 방문하는 조건이 있기 때문에 각 정점별 인접 노드 번호를 오름차순으로 정렬해주어야한다. 개인적으로 반복문을 이용하여 구현하는 BFS보다 재귀함수를 이용해야하는 DFS가 조금 더 익숙치 않아 어려운 것 같다. 현재 노드를 방문처리하고 인접 노드를 검사하는 것까지는 동일하지만 DFS에서는 인접 노드가 방문되지 않은 노드라면 해당 노드를 재귀호출하고 BFS에서는 인접 노드가 ..
[이코테] 문제2 - 미로 탈출(152p) 풀이 시간: 40~45분 이내 1) 문제 해결 아이디어 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다. 상하좌우로 연결된 모드 노드의 길이가 1로 동일하므로 (1, 1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결 가능함 1. 종료 조건 설정 항상 출구값을 리턴하기 때문에 종료 조건이 없어도 결과는 똑같다. 다만 종료 조건을 넣어주면 해당 좌표가 출구지점이 될 떄 까지만 탐색을 진행한다. 2. 탐색 조건에서 시작점 제외 상하좌우 탐색 시, 시작점은 갔던 곳이므로 탐색하지 않도록 조건을 설정하였다. 책의 코드처럼 시작점일 때도 탐색하게 해도 결과값은 달라지지 않지만 값이 3으로 덮어쓰여지게 된다. 1. 시작..
