[백준] 16930번 - 달리기 풀이 시간: 3시간 이내 아이디어를 떠올리고 코드를 짜는데는 30분 밖에 안걸렸지만 시간 초과를 고치는데 시간이 좀 걸린 문제다. 지금까지 내가 겪었던 시간 초과 문제들에서 보통은 몇가지 방법들을 쓰면 해결이 되었는데 이 문제는 설계를 꼼꼼하게 하지 못해 일어난 시간초과 문제로 해결하기가 힘들었다. 꼭 복습이 필요한 문제!! 매 초마다 상하좌우 중 1가지 방향으로 이동할 수 있고 최소 1개~최대 K개의 빈칸을 이동할 수 있다. 시작점에서 도착점까지 이동하는 최소 시간을 구하는 문제로 BFS로 풀 수 있는 문제이다. 일반적인 BFS 문제는 상하좌우로 한 칸씩만 이동할 수 있으나 이 문제는 상하좌우로 (1~K)칸의 연속된 빈칸을 이동할 수 있다는 것이 중요 포인트다. (풀이1..
[백준] 9205번 - 맥주 마시면서 걸어가기 풀이 시간: 90분 이내 1) 문제 해결 아이디어 이 문제는 방향벡터(dx, dy)등을 이용하여 최단 경로를 찾는 문제가 아니기때문에 편협한 사고방식으로는 BFS로 풀어야겠다고 바로 떠올리기가 쉽지 않은 문제였다. 추후 복습이 꼭 필요한 문제! 오늘의 교훈: 방향벡터를 사용하지 않는 문제도 BFS로 풀 수 있다!! 처음에는 단순하게 각 좌표들을 x, y 기준 오름차순으로 정렬하고 for문을 돌려서 현재 지점과 다음 지점의 거리(x 좌표의 차이 + y 좌표의 차이)가 1000이 넘으면 바로 종료하게 설계했다. 그런데 생각해보니 그렇게 정렬을 하면 오류가 있다는 사실을 알아냈다. 예를 들어, 아래와 같이 입력받았다고 하자. 현재 지점: (0, 0) 편의점: (5..
[백준] 14226번 - 이모티콘 풀이 시간: 70분 이내 1) 문제 해결 아이디어 문제 아이디어를 떠올리고 구현을 하는 것 자체는 30분도 안걸렸는데 오류를 고치느라 시간이 오래걸렸다. 초기 화면에 이모티콘 1개가 입력된 상태에서 3가지 연산을 이용해 이모티콘을 S개를 만드는데 걸리는 최소 시간을 구하는 문제다. 최소 시간을 구하는 문제이니 BFS를 이용하였고 이 문제를 푸는데 중요한 포인트는 3가지 연산을 수식화하는 것이다!! 1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. (screen, board) → (screen, screen) 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. (screen, board) → (screen + baord, board) 3. 화면에 있..
[백준] 1707번 - 이분 그래프 풀이 시간: 60분 이내 1) 문제 해결 아이디어 아이디어를 떠올리기 굉장히 어려웠던 문제다. 아이디어만 쉽게 떠올렸다면 구현하는데는 오래 걸리지 않은 문제다. 하지만 추후 복습이 필요한 문제! 일단 이분 그래프에 대해서 정확한 이해가 필요하다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 즉, 그래프의 정점을 두가지 색으로 칠한다고 했을 때, 인접한 정점끼리는 다른 색을 가지고 있는 그래프가 이분 그래프다. 1. 시작점 삽입, 방문 처리 (시작점은 0으로 방문 처리함) 2. 인접노드들에 대해 반복 2-1. 방문하지 않은 노드..
[백준] 2589번 - 보물섬 풀이 시간: 20분 이내 1) 문제 해결 아이디어 이 문제는 보물이 묻혀있는 두 곳 간의 최단 거리로 이동하는 시간을 문제로 BFS로 풀이가 가능하다. 일단 보물은 육지에 묻혀있을 수 있기 때문에 for문을 돌려 육지인 모든 칸에 대해서 bfs()를 호출하여 모든 경우를 검사해보아야 한다. 여기서 보물은 최단 거리로 이동한다고 가정했을 때 가장 오랜 시간이 걸리는 곳이어야 한다. 그러므로 하나의 보물이 시작점에 있다고 보면 다른 보물은 시작점에서 bfs를 했을 때 기록된 visited의 값 중 최댓값에 위치해야 한다. 두 보물 사이의 최단 거리는 (최댓값 - 1) 이므로 이 값을 리턴하고 종료한다. 그렇게 모든 육지 칸에 대해 bfs를 돌려 얻은 값들 중 최댓값이 이 문제의..
[백준] 1926번 - 그림 풀이 시간: 10분 이내 아주 쉽게 해결할 수 있었던 문제이다. 그림의 개수와 그 중 가장 넓은 그림의 넓이를 출력하는 문제로 BFS, DFS로 모두 풀이가 가능한 유형이다. 하지만 다른 사람들의 DFS 풀이를 찾아봐도 시간초과나 메모리초과 문제가 다수가 발생했다. 아래 글에 따르면 DFS에서 방향벡터를 이용해 for문을 돌리지 않으면 메모리 초과가 뜨지 않았지만 이런 문제의 경우 그냥 BFS로 풀이하는 것이 좋을 듯 하다. DFS는 재귀 방식으로 수행되기 때문에 호출할 때마다 스택에 쌓여 메모리를 많이 차지하게 되고 BFS는 큐에 쌓이는 객체의 크기가 크지 않다면 훨씬 적은 비용이 발생하므로 메모리 측면에서 유리할 수 있다. 오늘의 교훈! 상황에 따라 DFS, BFS 풀이를..
[백준] 17086번 - 아기 상어2 풀이 시간: 40분 이내 유사 문제: 7576번 https://hseungyeon.tistory.com/217 [DFS/BFS/완전탐색] ▲ 7576번 - 토마토 [백준] 7576번 - 토마토 풀이 시간: 40분 이내 1) 문제 해결 아이디어 토마토가 모두 익을 때까지 최소 날짜를 구하는 문제다. 익은 토마토가 상하좌우로 인접한 위치에 있는 익지 않은 토마토를 hseungyeon.tistory.com N * M의 맵에서 상어 위치 기준 둘러싼 8개의 좌표로 이동이 가능하다. 이 문제는 처음에 BFS로 풀어야 하나 싶지만 1개 이상의 상어에서 가장 멀리 떨어진 칸을 찾는 문제로 BFS로 풀어야하는 문제이다. (풀이1) 시간 초과한 코드(0인 곳에서 bfs 호출) 1) ..
[백준] 1303번 - 전쟁 - 전투 풀이 시간: 15~20분 이내 정석대로만 풀면 아주 쉽게 풀 수 있는 문제로 DFS, BFS 풀이가 모두 가능하다. DFS 풀이가 시간, 메모리 효율이 더 뛰어나다. (풀이1) BFS 1) 문제 해결 아이디어 2) 소스코드 from collections import deque # BFS def bfs(x, y, color): cnt = 0 # 병사 수 queue = deque() # 시작 지점 삽입, 방문 처리 queue.append((x, y)) graph[x][y] = 0 while queue: x, y = queue.popleft() cnt += 1 for i in range(4): nx = x + dx[i] ny = y + dy[i] if(0
