📖 문제[백준] #2644. 촌수계산 (DFS/BFS) (파이썬/Python)난이도: 실버2문제 유형: DFS/BFS📌 문제 요약`a`, `b`의 촌수를 계산하는 문제이다. 그래프로 따지면 `a`노드와 `b`노드 사이의 간선의 개수를 구하면 된다.만약 그래프가 연결되어 있지 않다면 `-1`을 출력한다.🔍 문제 접근💡 문제 분석DFS와 BFS 모두 풀이 가능하다.이 문제에서는 노드 a와 b 사이의 간선 개수를 구하는 게 목적이기 때문에 깊이 우선 탐색을 사용하는 DFS가 더 적합하다고 판단했다. 또한, 이 문제는 경로를 탐색하면서 불필요한 경로는 제외하는 백트래킹 기법이 더 적합하다. 백트래킹을 통해 불필요한 경로를 가지치기하면서 효율적으로 두 노드 간의 촌수를 계산할 수 있다. 💡 백트래킹백트래..

📖 문제[백준] #5014. 스타트링크 (파이썬/Python)난이도: 실버1유형: BFS📌 문제 요약강호는 스타트업 스타트링크 면접에 늦게 도착해, 건물의 엘리베이터를 타고 이동하려 한다.건물은 총 `F`층이며, 강호는 현재 `S`층에 있다. 면접장은 `G`층이다.엘리베이터에는 버튼이 두 개뿐이다.`U` 버튼: 위로 `U`층 이동`D` 버튼: 아래로 `D`층 이동강호가 `G`층에 도착하려면 버튼을 최소 몇 번 눌러야 하는지 구해야 한다.만약 도착할 수 없다면 `"use the stairs"`를 출력한다.🔍 문제 접근💡 문제 분석“최소 버튼 클릭 횟수” → 최단 거리 문제이다.따라서 BFS(너비 우선 탐색)으로 접근한다.F층: 사무실의 총 층수G층: 스타트링크가 있는 곳의 위치 S층: 강호가 지금 ..

📖 문제[백준] #2468. 안전 영역 (파이썬/Python)난이도: 실버1유형: DFS, BFS📌 문제 요약장마철을 대비해 지역의 높이 정보를 기반으로 비가 내렸을 때 물에 잠기지 않는 안전한 영역의 최대 개수를 계산해야 한다.지역은 N x N 크기의 2차원 배열로 주어진다.비가 많이 오면 특정 높이 이하의 지점들은 잠긴다.이때 상하좌우로 인접해 있는 잠기지 않은 지점들을 하나의 안전한 영역으로 간주한다.비의 양에 따라 잠기는 범위가 달라지므로, 모든 비의 양에 대해 안전 영역의 개수를 구하고, 그 중 최대값을 출력해야 한다.높이는 1 이상 100 이하의 자연수이며, 잠기지 않는 경우도 고려해야 한다.🔍 문제 접근💡 문제 분석물에 잠기지 않는 안전한 영역이란, 인접한 지점들이 연결된 덩어리로 존..

📖 문제[프로그래머스] [2021 카카오 채용연계형 인턴십] 거리두기 확인하기 (파이썬/Python)난이도: Level 2유형: 완전탐색, BFS 문제 요약개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔다. 코로나 바이러스 감염 예방을 위해, 응시자들은 대기실에서 일정한 거리를 두고 앉아야 한다. 각 대기실은 5x5 크기로, 총 5개의 대기실이 주어진다. 규칙 요약:응시자끼리는 맨해튼 거리 2 이하로 앉으면 안 된다.단, 거리 2 이내라도 파티션(X) 으로 막혀 있다면 예외적으로 허용한다. 문자 의미:`P`: 사람이 앉아있는 자리`O`: 빈 테이블`X`: 파티션 문제 요구사항:5개의 대기실이 2차원 문자열 배열 형태로 주어진다.각 대기실에 대해 거리두기를 지키고 있다면 `1`, 위반한 사람이 단 한..

📖 문제[프로그래머스] 게임 맵 최단거리 (파이썬/Python) (자바/Java)난이도: Level 2유형: BFS풀이 시간: 28분문제 요약캐릭터가 `(1,1)`에서 시작해 상대 팀 진영 `(n,m)`까지 이동해야 한다.이동할 수 있는 곳은 1, 이동할 수 없는 벽은 0으로 표시된다.최소 칸 수로 상대 진영에 도착하는 경우의 칸 수를 반환하라.도달할 수 없다면 -1을 반환한다.캐릭터는 상하좌우 네 방향으로 한 칸씩 이동 가능하다.맵 밖으로 나갈 수 없고, 벽(0)은 통과할 수 없다.🔍 문제 접근💡 문제 분석핵심 키워드: 최단거리, 동서남북으로 이동 ⇒ BFS 유형!동서남북으로 인접한 칸만 탐색할 수 있다.`maps`에는 0이 벽을 의미하고 1이 벽이 없는 자리를 의미한다.즉, 매번 이동할 때마다 ..

📖 문제[백준] #13549. 숨바꼭질 3 (파이썬/Python)난이도: 골드5유형: BFS문제 요약수빈이는 현재 위치 `N`에 있고, 동생은 `K`에 있다.수빈이는 다음 3가지 방법으로 이동할 수 있다.`X - 1` (1초 소요)`X + 1` (1초 소요)`2 * X` (0초 소요)목표는 동생에게 도달하는 데 걸리는 최소 시간(초)을 구하는 것이다.(숨바꼭질 시리즈)🔍 문제 접근💡 문제 분석처음에 틀린 이유를 찾을 수가 없어서 GPT의 도움을 받았다.이 문제는 가중치가 0 또는 1인 그래프에서의 최단 거리 문제이다.`X → 2X`는 이동 시간 0 → 가중치 0`X → X±1`은 이동 시간 1 → 가중치 1이처럼 간선 가중치가 0 또는 1일 경우, 일반 BFS가 아닌 0-1 BFS 기법을 사용해야 ..

📖 문제[백준] #14226. 이모티콘 (파이썬/Python)난이도: 골드4유형: BFS문제 요약현재 화면에는 😃 이모티콘 1개가 있다.목표: S개의 이모티콘을 화면에 만들기 위한 최소 시간을 구해야 한다.사용할 수 있는 연산은 다음 3가지이다. (모두 1초 소요)연산 설명1. 복사화면에 있는 이모티콘 전부를 클립보드에 복사2. 붙여넣기클립보드 내용을 화면에 붙여넣기3. 삭제화면에서 이모티콘 하나 삭제※ 클립보드가 비어있으면 붙여넣기를 할 수 없다.※ 클립보드, 화면 모두 "일부 선택"은 불가능하며 전량 복사/붙여넣기/삭제만 가능하다.🔍 문제 접근💡 문제 분석"최소 시간" → BFS로 탐색해야 한다.일반적인 BFS와 달리, 상태를 구성하는 요소가 2가지이다.현재 화면 이모티콘 수현재 클립보드 이모..

📖 문제[백준] #1697. 숨바꼭질(파이썬/Python)난이도: 실버1유형: BFS문제 요약수빈이는 현재 위치 `N`에 있고, 동생은 `K`에 있다.수빈이는 다음 3가지 방법으로 이동할 수 있다.`X - 1` (1초 소요)`X + 1` (1초 소요)`X * 2` (1초 소요)목표는 수빈이가 동생을 찾는 가장 빠른 시간을 구해야 한다.(이 문제는 시리즈 문제로, 숨바꼭질 2, 3, 4문제도 있으니 함께 풀어보는 것을 추천한다)🔍 문제 접근💡 문제 분석가장 빠른 시간을 찾는 문제 → BFS로 탐색으로 탐색해야 한다는 것을 알 수 있다.BFS의 레벨이 곧 최단시간이다.BFS는 가까운 노드부터 탐색하기 때문에, 특정 위치에 도달하는 가장 빠른 시간을 구하는 데 적합하다. 🧠 풀이 아이디어BFS 로직은 ..

📖 문제[백준] #12851. 숨바꼭질 (파이썬/Python)난이도: 골드4유형: BFS문제 요약수빈이는 현재 위치 N에 있고, 동생은 K에 있다.수빈이는 다음 3가지 방법으로 이동할 수 있다.X - 1 (1초 소요)X + 1 (1초 소요)X * 2 (1초 소요)목표는 수빈이가 동생을 찾는 가장 빠른 시간과, 그 시간 안에 동생을 찾는 방법의 수를 구하는 것이다.🔍 문제 접근💡 문제 분석최단 시간 → BFS로 탐색"경로 수"까지 구해야 하므로, 같은 노드에 여러 경로로 도달할 수 있음을 고려해야 한다.중복 방문 방지 + 경로 수 누적 = `dist`, `ways` 배열 사용 🧠 풀이 아이디어`dist[x]`: `x` 지점까지 도달하는 데 걸리는 최단 시간`ways[x`]: `x` 지점에 최단 시간..