당근마켓 엔지니어 문제 질문!
90
작성한 질문수 6
안녕하세요 코드를 짜던중에 뭔가 의도대로 안되어 질문드립니다.
문제를 보고 생각해서 아래와 같이 만들었는데요.
이후 쌤의 정답과 비교해도 어느 부분이 달라서 의도대로 안되는지 궁금합니다.
#include <bits/stdc++.h>
using namespace std;
int n, m, ret, qx, qy, nx, ny, sx, sy, cx, cy;
int visited[101][101];
int a[101][101];
vector<int> adj[101];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
void bfs(int y, int x){
queue<pair<int,int>> q;
visited[y][x] = 1;
q.push({y, x});
while(q.size()){
tie(qy, qx) = q.front(); q.pop();
for(int i = 0; i < 4; i++){
ny = qy + dy[i];
nx = qx + dx[i];
if(ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 0) continue;
if(visited[ny][nx]) continue;
visited[ny][nx] = visited[qy][qx] + 1;
q.push({ny,nx});
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> a[i][j];
}
}
cin >> sy >> sx;
cin >> cy >> cx;
bfs(sy,sx);
cout << visited[cy][cx] << "\n";
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cout << visited[i][j] << ' ';
}
cout << "\n";
}
}
답변 2
0
안녕하세요 호준님 ㅎㅎ
이후 쌤의 정답과 비교해도 어느 부분이 달라서 의도대로 안되는지 궁금합니다.
-> 어떤 부분이 다른가요?
감사합니다.
0
안녕하세요 쌤
문제를 보고 저는 위와 같이 코드를 작성했고, 입력을 해봤는데 정답과 다르다는 이야기였습니다.
코드를 비교해봐도 정답이 안나오는데 디버깅이 익숙치 않아 어디가 잘못됐는지 궁금하여 질문드렸습니다.
감사합니다!
===입력===
5 5
0 0
4 4
1 0 1 0 1
1 1 1 0 1
0 0 1 1 1
0 0 1 1 1
0 0 1 1 1
===출력===
2
0 1 2 3 4
0 2 0 4 5
4 3 0 5 0
0 4 5 6 0
0 5 6 7 0
0
안녕하세요 호준님 ㅎㅎ
입력순서가 잘못되었습니다.
cin >> n >> m;
cin >> sy >> sx;
cin >> cy >> cx;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> a[i][j];
}
}이렇게 고쳐보시겠어요?
0
안녕하세요, 인프런 AI 인턴입니다.
이호준님, 작성해주신 코드를 기반으로 BFS 알고리즘을 사용하여 경로를 찾고자 하시는 것 같네요. 코드를 살펴본 결과, 몇 가지 점검해볼 부분을 제안드립니다.
문제 분석 및 코드 검토
초기화 문제: BFS 알고리즘에서 출발점을 기준으로 모든 경로를 탐색하는데,
visited배열이 적절히 초기화되지 않거나 특정 지점에서 반복적으로 방문이 발생하는 경우 원하는 결과를 얻기 어려울 수 있습니다. 출발점에서 도착점까지의 최단 경로를 찾는 것이 목적이라면visited배열이 정확히 방문 여부만을 저장하기보다, 몇번의 이동을 통해 해당 지점에 도달했는지를 기록하고 있는지가 중요합니다. 현재 코드는visited[y][x] = 1로 시작하므로 첫 방문이 곧 경로의 길이가 됩니다.경계 체크: BFS 탐색에서의 유효한 움직임을 위해 배열의 경계 체크를 꼼꼼히 해야 합니다. 초기코드에서는 조건문들을 통해 배열의 경계와 장애물을 적절히 피하는 코드가 작성되어 있습니다만, 어떤 경우에도
visited조건으로 인해 경로가 단절될 수 있는지 확인이 필요합니다.경로 추적:
visited배열 외에도 경로를 추적하기 위해 어느 지점에서 이동해왔는지를 저장하는 추가적인 자료 구조를 고려해보시는 것도 좋습니다. 이는 나중에 어떤 경로로 이동했는지를 확인할 때 도움이 됩니다.출력 검증: 실제로
bfs함수가 무사히 전체 맵을 탐색하고 있으며,visited[cy][cx]가 의도한 결과를 출력하고 있는지 확인해 보세요. BFS가 종료된 후visited배열을 출력해보며 모든 경로가 적절히 탐색되었는지 디버깅하는 것도 유용할 수 있습니다.
추가 참고 자료
A 시작점부터 가능 경로 탐색, BFS를 활용한 경로 최적화 내용을 참고해보시면 유사한 문제에서 코드 최적화 및 디버깅 방법에 대해 도움이 될 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
코딩테스트 참고문헌 질문
0
28
2
4-P 질문 있습니다.
0
33
3
4-N 문제 수정 요청
0
29
1
2-T 질문
0
38
1
코딩 살구클럽 가입 문의
0
74
2
코딩살구클럽 가입문의
0
79
2
3-K private case 질문
0
76
2
안녕하세요. 코딩살구클럽 문의드립니다!
0
86
2
7:41 듣다가 질문합니다
0
92
2
코드 리뷰 요청드립니다!
0
87
2
코딩살구클럽 계정 문의
0
84
2
SK하이닉스 대비 강의수강
0
226
3
코딩살구클럽 등록부탁드립니다.
0
81
2
7-F 재귀로 풀시 런타임애러
0
82
1
1-N 문제 질문입니다. (+ 채점오류)
0
86
2
코딩살구클럽 가입 확인 부탁드립니다.
0
88
2
직장인 코테 합격 공부방법 문의
0
136
2
코딩살구클럽 가입 방법
0
104
2
6-H 체점 관련 질문
0
83
1
채점서버 연결 관련 질문입니다
0
111
2
삼성 s직군
0
95
1
삼성 코테 없어짐
0
236
1
코딩살구클럽 가입부탁드립니다
0
92
2
코딩살구클럽 가입 요청 확인부탁드립니다
0
77
2





