κΉμ΄/λλΉ μ°μ νμ(DFS/BFS) : κ²μ 맡 μ΅λ¨κ±°λ¦¬
λ¬Έμ μΆμ² - νλ‘κ·Έλλ¨Έμ€ μ½λ©ν μ€νΈ κ³ λμ Kit
λ¬Έμ μ€λͺ
ROR κ²μμ λ νμΌλ‘ λλμ΄μ μ§ννλ©°, μλ ν μ§μμ λ¨Όμ νκ΄΄νλ©΄ μ΄κΈ°λ κ²μμ λλ€. λ°λΌμ, κ° νμ μλ ν μ§μμ μ΅λν 빨리 λμ°©νλ κ²μ΄ μ 리ν©λλ€.
μ§κΈλΆν° λΉμ μ ν νμ νμμ΄ λμ΄ κ²μμ μ§ννλ €κ³ ν©λλ€. λ€μμ 5 x 5 ν¬κΈ°μ 맡μ, λΉμ μ μΊλ¦ν°κ° (ν: 1, μ΄: 1) μμΉμ μκ³ , μλ ν μ§μμ (ν: 5, μ΄: 5) μμΉμ μλ κ²½μ°μ μμμ λλ€.
μ κ·Έλ¦Όμμ κ²μμ λΆλΆμ λ²½μΌλ‘ λ§νμμ΄ κ° μ μλ κΈΈμ΄λ©°, ν°μ λΆλΆμ κ° μ μλ κΈΈμ
λλ€. μΊλ¦ν°κ° μμ§μΌ λλ λ, μ, λ¨, λΆ λ°©ν₯μΌλ‘ ν μΉΈμ© μ΄λνλ©°, κ²μ 맡μ λ²μ΄λ κΈΈμ κ° μ μμ΅λλ€.
μλ μμλ μΊλ¦ν°κ° μλ ν μ§μμΌλ‘ κ°λ λ κ°μ§ λ°©λ²μ λνλ΄κ³ μμ΅λλ€.
- 첫 λ²μ§Έ λ°©λ²μ 11κ°μ μΉΈμ μ§λμ μλ ν μ§μμ λμ°©νμ΅λλ€.
- λ λ²μ§Έ λ°©λ²μ 15κ°μ μΉΈμ μ§λμ μλν μ§μμ λμ°©νμ΅λλ€.
μ μμμμλ 첫 λ²μ§Έ λ°©λ²λ³΄λ€ λ λΉ λ₯΄κ² μλν μ§μμ λμ°©νλ λ°©λ²μ μμΌλ―λ‘, μ΄ λ°©λ²μ΄ μλ ν μ§μμΌλ‘ κ°λ κ°μ₯ λΉ λ₯Έ λ°©λ²μ λλ€.
λ§μ½, μλ νμ΄ μμ μ ν μ§μ μ£Όμμ λ²½μ μΈμλμλ€λ©΄ μλ ν μ§μμ λμ°©νμ§ λͺ»ν μλ μμ΅λλ€. μλ₯Ό λ€μ΄, λ€μκ³Ό κ°μ κ²½μ°μ λΉμ μ μΊλ¦ν°λ μλ ν μ§μμ λμ°©ν μ μμ΅λλ€.
κ²μ 맡μ μν mapsκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μΊλ¦ν°κ° μλ ν μ§μμ λμ°©νκΈ° μν΄μ μ§λκ°μΌ νλ μΉΈμ κ°μμ μ΅μκ°μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ. λ¨, μλ ν μ§μμ λμ°©ν μ μμ λλ -1μ return ν΄μ£ΌμΈμ.
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
int visited[102][102]={0,};
int re[102][102]={0,};
int solution(vector<vector<int> > maps){
int n = maps.size();
int m=maps[0].size();
int answer = 0;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
queue<pair<int,int> > q;
q.push({0,0});
re[0][0]=1;
while(!q.empty()){
pair<int,int> a = q.front();
q.pop();
for(int i=0; i<4; ++i){
int nx=a.first+dx[i];
int ny=a.second+dy[i];
if(nx<0||ny<0||nx>=n||ny>=m) continue;
else if(visited[nx][ny]==1) continue;
else if(maps[nx][ny]==0) continue;
else{
q.push({nx,ny});
visited[nx][ny] = 1;
re[nx][ny] = re[a.first][a.second]+1;
}
}
}
if(re[n-1][m-1]==0) re[n-1][m-1]=-1;
answer = re[n-1][m-1];
return answer;
}
'π μκ³ λ¦¬μ¦ > Programmers' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[C++/PGS] Lv.3 : λ€νΈμν¬ (DFS/BFS) (0) | 2023.02.23 |
---|---|
[C++/PGS] Lv.2 : νκ² λλ² (DFS) (0) | 2023.02.23 |
[PGS] Lv.0 (μ½λ©ν μ€νΈ μ λ¬Έ) 12μΌμ°¨ λ¬Έμ (0) | 2023.02.20 |
[PGS] Lv.0 (μ½λ©ν μ€νΈ μ λ¬Έ) 11μΌμ°¨ λ¬Έμ (0) | 2023.02.20 |
[PGS] Lv.0 (μ½λ©ν μ€νΈ μ λ¬Έ) 10μΌμ°¨ λ¬Έμ (0) | 2023.02.20 |