[백준] 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에서는 인접 노드가 ..
[백준] 2873번 - 롤러코스터 풀이 시간: 6~7 시간 1) 문제 해결 아이디어 아이디어를 떠올리는데 어려움을 겪은 문제다. 케이스를 분류하고 일반화하기가 까다로운 문제로 지금까지 풀었던 그리디 문제 중에는 제일 어려운 문제인 것 같다. 특히나 r, c가 모두 짝수인 경우가 구현하기 가장 까다롭기 때문에 푸는데 실패를 계속 겪고 정답이 되기까지 시간이 오래걸렸다. 각 칸은 한 번만 방문할 수 있고 지나간 칸의 합이 가장 최대가 되는경로를 출력하는 문제다. 지나간 칸의 합이 가장 최대가 되기 위해서는 최대한 많은 칸을 지나가야한다. 이 문제는 r, c가 짝수인지 홀수인지에 따라서 케이스를 분리하는 것이 중요 포인트다. 3번째 케이스같은 경우는 제외할 1칸을 어떻게 설정할지를 떠올리는 것이 중요하다. 그..
[백준] 12845번 - 모두의 마블 풀이 시간: 30~35분 이내 (풀이1) 문제 그대로 구현한 방법 1) 문제 해결 아이디어 아이디어를 떠올리는 것은 어렵지 않았으나 계속 런타임 에러(TypeError)가 났다. 주어진 테스트 케이스에서는 값이 잘 나왔으나 다른 테스트 케이스의 경우 제대로 된 값이 오류가 발생했다. 1. 두 카드는 인접한 카드 2. 합성한 카드 A의 레벨은 변하지 않음 카드를 합성할 때마다 카드A, B 레벨의 합만큼 골드를 받음 1. 레벨의 최댓값(max)를 기준으로 계속 오른쪽으로 합성하기(최댓값의 인덱스가 맨 마지막이 될 때까지) 2. 최댓값(max)기준으로 계속 왼쪽으로 합성하기(남은 카드가 1개가 될 때까지) 첫번째 오류. 리스트 값 삭제 후 리스트 길이에 대한 처리 리스트 ..
[백준] 11256번 - 사탕 풀이 시간: 10~15분 이내 1) 문제 해결 아이디어 문제 설명대로 코드를 구현하기만 하면 풀 수 있는 쉬운 문제였다. 박스 크기(r, c)에 담을 수 있는 최대 사탕 개수는 (r * c)이다. 최소한의 상자 개수는 박스 부피(volume)가 큰 상자부터 사탕을 담는 것이다. 그래서 입력받은 상자(box)들을 부피 기준으로 내림차순 정렬해주었다. 2) 소스코드 t = int(input()) # 테스트 케이스 수 for i in range(t): j, n = map(int,input().split()) # 사탕 개수, 상자 개수 box = [] # n개의 박스 크기 res = 0 # 박스 개수 for _ in range(n): box.append(list(map(int, i..
