🔵 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/1844
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
🔵 문제 풀이
아주 기초적인 bfs 문제로, bfs의 특성을 활용하여 목적지까지 최단 거리를 찾는 문제이다.
주의해야 할 점은 n과 m이 서로 다를 수도 있으므로 행과 열을 헷갈리지 않는 것이다.
🔵 전체 코드
#include <vector>
#include <queue>
using namespace std;
// 그냥 bfs 문제
// n과 m은 다르다. (행, 열 헷갈리지 않게 주의)
int solution(vector<vector<int>> maps)
{
const int ROW = maps.size(); // 행 (세로)
const int COL = maps[0].size();
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
vector<vector<int>> visited(ROW, vector<int>(COL, -1));
queue<pair<int, int>> q;
q.push({ 0, 0 });
visited[0][0] = 1;
while (!q.empty())
{
int r = q.front().first;
int c = q.front().second;
q.pop();
if (r == ROW - 1 && c == COL - 1)
return visited[r][c];
for (int i = 0; i < 4; i++)
{
int nr = r + dx[i];
int nc = c + dy[i];
if (nr < 0 || nc < 0 || nr >= ROW || nc >= COL) continue;
if (maps[nr][nc] == 0 || visited[nr][nc] != -1) continue;
q.push({ nr, nc });
visited[nr][nc] = visited[r][c] + 1;
}
}
return -1;
}
🔵 시간 복잡도
maps의 크기를 n * m이라 할 때, bfs는 모든 노드를 한 번씩 확인하므로 최종 시간 복잡도는 O(N * M)이다.
'PS' 카테고리의 다른 글
| [C++] Programmers Lv. 3 "양과 늑대" (0) | 2025.06.17 |
|---|---|
| [C++] Programmers Lv. 3 "네트워크" (0) | 2025.06.13 |
| [C++] Programmers Lv. 2 "미로 탈출" (0) | 2025.06.10 |
| [C++] 다익스트라 & 벨만-포드 알고리즘 구현하기 (0) | 2025.06.10 |
| [C++] Programmers Lv. 3 "섬 연결하기" (0) | 2025.06.05 |