인프런 커뮤니티 질문&답변

yhm1620님의 프로필 이미지

작성한 질문수

코딩테스트 실전 모의고사(with C++) : 대기업 대비

4. 제품이동 코드해설(결정알고리즘, BFS)

선생님 안녕하세요. 다른 풀이에 대한 질문이 있습니다.

작성

·

169

0

안녕하세요. 항상 좋은 강의 감사드립니다.
 
문제에서는 vector<pair<int, int>>를 쓰셨는데, 저는 2차원 배열을 이용해서 풀어보았습니다.
 
#include <bits/stdc++.h> using namespace std; int board[10001][10001]; int n, m, s, e; int can(int w) { queue<int> Q; int ch[10001]; for (int i = 0; i < 10; i++) cout << ch[i] << " "; cout << endl; ch[s] = 1; cout << "앞부분 ch[e] : " << ch[e] << endl; Q.push(s); while(!Q.empty()) { int v = Q.front(); Q.pop(); for(int i = 0; i < 10; i++) { if(board[v][i] >= w && ch[i] == 0) { cout << "여기 옴" << endl; cout << v << " " << i << endl; ch[i] = 1; Q.push(i); } } } cout << "ch[e] : " << ch[e] << endl; return ch[e]; } int main() { ios_base::sync_with_stdio(false); freopen("input.txt", "rt", stdin); int lt = 1, rt = 1000000000, mid, res; cin >> n >> m; for(int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; board[a][b] = c; } cin >> s >> e; while(lt <= rt) { mid = (lt + rt) / 2; if(can(mid)) { cout << "mid : " << mid << endl; res = mid; lt = mid + 1; } else { cout << "else mid : " << mid << endl; rt = mid - 1; } } cout << res; return 0; }
 
실행해보시면 답이 6이 나오는데, ch 배열이 새로 선언되어도 그 전의 값을 그대로 가지고 있는 것 같네요.
 
이 현상의 원인에 대해 질문드리고 싶습니다!

 

실행

답변 1

0

yhm1620님의 프로필 이미지
yhm1620
질문자

#include <bits/stdc++.h>

using namespace std;

 

int board[10001][10001];

int n, m, s, e;

 

int can(int w) 

{

  queue<int> Q;

  vector<int> ch(10001, 0);

 

  ch[s] = 1;

  Q.push(s);

while(!Q.empty())

{

int v = Q.front();

Q.pop();

for(int i = 1; i < 10001; i++)

{

if(board[v][i] >= w && ch[i] == 0)

{

//cout << v << " " << i << endl;

ch[i] = 1;

Q.push(i);

}

}

}

return ch[e];

}

 

int main()

{

ios_base::sync_with_stdio(false); 

freopen("input.txt", "rt", stdin);

int lt = 1, rt = 1000000000, mid, res;

cin >> n >> m;

for(int i = 1; i <= m; i++)

{

int a, b, c;

cin >> a >> b >> c;

board[a][b] = c;

board[b][a] = c;

}

cin >> s >> e;

while(lt <= rt)

{

mid = (lt + rt) / 2;

if(can(mid))

{

//cout << "mid : " << mid << endl;

res = mid;

lt = mid + 1;

}

else

{ //cout << "else mid : " << mid << endl;

rt = mid - 1; 

}

}

cout << res;

return 0;

}

 

yhm1620님의 프로필 이미지

작성한 질문수

질문하기