[백준] 10451번 - 순열 사이클 풀이 시간: 20분 이내 매번 위치벡터를 이용한 DFS/BFS문제를 풀다가 오랜만에 그래프 문제를 만나 평소보다 조금 시간이 걸리긴 했지만 쉽게 풀 수 있는 문제였고 DFS, BFS 중 편한 방식으로 풀면 된다. 이 문제의 경우 메모리, 시간 측면에서 모두 DFS로 푸는 것이 더 효율적인 결과가 나왔기 때문에 DFS로 푸는 것을 추천한다. (풀이1) DFS 1) 문제 해결 아이디어 2) 소스코드 t = int(input()) # 테스트 케이스 수 # DFS def dfs(v): visited[v] = True # 현재노드 방문처리 nv = graph[v] # 인접 노드 # 아직 방문하지 않은 노드라면 dfs 호출 if not visited[nv]: dfs(nv) fo..
[백준] 2151번 - 거울 설치 풀이 시간: 3시간 이내 유사 문제: 2206 https://hseungyeon.tistory.com/223 [DFS/BFS/완전탐색] ★★ 2206번 - 벽 부수고 이동하기(BFS) [백준] 2206번 - 벽 부수고 이동하기 풀이 시간: 1) 문제 해결 아이디어 언제 벽을 부숴야 할지 조건을 떠올리는게 쉽지 않았다. 최근에 푼 BFS 문제 중에는 난이도가 가장 높은 문제인 것 같다. hseungyeon.tistory.com 1) 문제 해결 아이디어 문제를 읽었는데 문제 이해가 가질 않아서 15분정도 고민하다가 검색을 했고 도움을 받았다. 문제 자체가 이해가 가지 않아 어려움을 겪은 문제였다. 문제를 다 이해하고나서도 여러가지 오류를 해결하는데 시간이 오래걸렸기 때문에 ..
[백준] 4179번 - 불! 풀이 시간: 6시간 이내 유사한 문제: 3055 https://hseungyeon.tistory.com/241 [DFS/BFS/완전탐색] 3055번 - 탈출(BFS) [백준] 3055번 - 탈출 풀이 시간: 50분 이내 유사 문제: 4179 (풀이1) 물, 고슴도치 deque을 각각 생성한 방식(고슴도치→물 이동) 1) 문제 해결 아이디어 이 문제는 물이 차기 전에 고슴도치가 안전하 hseungyeon.tistory.com (풀이1) 실패한 코드 1) 문제 해결 아이디어 많이 어려웠던 문제로 추후 복습이 꼭 필요! 미로에서 지훈이의 위치와 불의 위치가 주어진다. 1분마다 지훈이는 상하좌우 중 1 방향으로 한 칸씩 이동하고 불은 상하좌우 4방향으로 1칸씩 이동한다. 지훈이가 불..
[백준] 3055번 - 탈출 풀이 시간: 50분 이내 유사 문제: 4179 (풀이1) 물, 고슴도치 deque을 각각 생성한 방식(고슴도치→물 이동) 1) 문제 해결 아이디어 이 문제는 물이 차기 전에 고슴도치가 안전하게 비버의 굴로 이동하기 위한 최소 시간을 구하는 문제로 BFS로 풀이가 가능하다. 혼자서 푸는데는 성공했지만 나중에 복습을 한번 해봐야할 문제! 매 분마다 고슴도치는 현재 있는 칸과 인접한 4칸 중 하나로 이동할 수 있고 물은 인접한 4방향으로 모두 이동한다. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없기 때문에 물→고슴도치 순으로 이동시켜야 하지만 고슴도치→물 순으로이동시켜도 전혀 문제가 되지 않는다. 그리고 고슴도치가 안전하게 비버의 굴로 이동할 수 없다면 "KAKTUS"를 출력해..
[백준] 2573번 - 빙산 풀이 시간: 90분 이내 1) 문제 해결 아이디어 일반적인 BFS문제와는 약간 다른 부분이 있었기 때문에 초반에 BFS로 푸는 것이 과연 효율적인가? 맞나? 싶었던 문제였다. 결국 혼자서 푸는데 성공하긴 했지만 추후 복습이 필요한 문제! 보통의 문제들은 입력받은 정보(graph), 방문여부체크(visited) 2개면 풀이가 가능하지만 이 문제의 경우에는 빙산 녹이기를 한 결과(result)가 추가적으로 필요하다. Q. 빙산 녹이기를 한 결과(result)를 사용해야하는 이유는? 빙산 녹이기를 한 칸의 결과값은 (기존값 - 상하좌우의 바다(0) 개수) 이다. 여기서 중요한 점은 빙산 한 칸을 녹이기를 한 결과를 바로 graph에 반영해버리면 다음 빙산인 칸이 그 칸과 인접한 칸..
[백준] 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. 화면에 있..
