인프런 커뮤니티 질문&답변
작성한 질문수
[4-D_1987_ 알파벳] bfs나 dfs로는 풀 수 없을까요?
해결된 질문
작성
·
292
·
수정됨
1
처음 최단 거리를 구하는 문제여서 bfs로 접근했습니다. 하지만 bfs로 최단거리를 구할 경우 방문한 알파벳을 다시 방문하면 안된다는 조건 때문에 최댓값이 이상하게 나와서 dfs로도 시도해봤습니다. dfs가 정답과 좀 더 가깝게 잘 짠 것 같은데 마지막 테스트 케이스를 통과하지 못하네요ㅜㅜ 뭔가 둘 다 visited 원복과 초기화가 잘 안되어서 그런 것 같은데 어떻게 해야할지 모르겠습니다 ㅠㅠ 이 코드를 어떻게 수정하면 좋을까요? ㅠㅠ
1. bfs
http://boj.kr/eab39a3f2732430eaa02117bc49541f6
dfs
답변 2
2
안녕하세요 효민님 ㅎㅎ
이 문제는 BFS든 DFS든으로. 풀면 안됩니다.
BFS와 DFS의 주요한 특징은
방문한 정점은 다시 방문하지 않는다는 점입니다.
이 문제 같은 경우 방문한 정점을 다시 방문해야 합니다.
모든 경우의 수를 계산해야 하기 때문에
A -> B -> C -> E와
A -> B -> C -> D
이런 경우의 수를 계산해야 하는 것이죠.
일단은 완탐 자체가 재귀이기 때문에 DFS 코드를 중심으로 수정하시는게 좋습니다.
int dfs(int y, int x, char c){
alpa[c-'A']=1;
for(int i=0; i<4; i++){
int ny= y+ dy[i];
int nx= x+ dx[i];
if(nx>m || nx<0 || ny >n || ny<0 ) continue;
if(visited[ny][nx]) continue;
if(alpa[mp[ny][nx]-'A']) continue;
visited[ny][nx] = 1
dfs(ny, nx,mp[ny][nx]);
alpa[mp[ny][nx]-'A']=0;
visited[ny][nx] = 0
ret = max(ret, visited[ny][nx]);
}
return ret;
}이런식으로 방문했네 안방문했네 식으로 수정해주셔야 합니다.
이렇게 생각하시면 좋아요.
만약 visited continue로만 하고 원복을 하지 않는다면
a, b, c 경로만 체크가 가능할겁니다.
물론
a, b, c, d도 가능하지만 그건 우리가 원하는 로직이 아니죠?
여기서 a, b, c와 a, b, d라는 경로를 우리는 확인하고 싶은 것이고.
그리러면 a, b, c에서 c부분에서 방문처리를 해제,
그리고 나서 다시 b로 와서 a, b, d로 가는 경로를 체크해야 하는 것이죠.
만약 c방문처리를 해놓았다면
a, b, d가 아니라 a, b, c, d 처럼 c를 방문한 것이 영향을 주는 상태가 되어버리게 됩니다.
이런 영향을 주는 상태를 지운다. 가 바로 원복입니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 효민님 ㅎㅎ
이렇게 고쳐보시겠어요?
int n,m,x,y,ret = 1;
string s;코드를 보시면 처음 한칸만 움직이고 움직일 수 없는경우 ret이 0에서 cnt인 1로 갱신이 안되서 해당 반례를 해결하지 못하기 때문에 벌어지는 것 같습니다.
이렇게 고쳐서 제출하시면 통과합니다.
또는.
ret과cnt의 max처리하는 부분을 다음처럼 앞단으로 올려서 해결할 수도 있습니다. 어차피 해당 정점에 방문한다면 함수자체가 호출되기 때문에 ret에는 무조건 갈 수 있는 정점들의 최댓값이 담기는 것은 자명하구요.
#include <bits/stdc++.h>
using namespace std;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
int n,m,x,y,ret = 1;
string s;
char mp[20][20];
int visited[20][20];
int alpa[26];
int cnt;
void go(int y, int x, char c, int cnt){
ret = max(ret, cnt);
for(int i=0; i<4; i++){
int ny= y+ dy[i];
int nx= x+ dx[i];
if(nx>=m || nx<0 || ny >=n || ny<0 || alpa[mp[ny][nx]-'A']) continue;
if(visited[ny][nx]) continue;
visited[ny][nx]=1;
alpa[mp[ny][nx]-'A']=1;
cnt++;
go(ny, nx,mp[ny][nx], cnt);
alpa[mp[ny][nx]-'A']=0;
visited[ny][nx]=0;
cnt--;
}
return;
}
int main(){
cin >> n >> m;
for(int i=0; i<n;i++){
cin >> s;
for(int j=0;j<m;j++){
mp[i][j]=s[j];
}
}
cnt=1; // 말이 지난 칸 수
visited[0][0]=1;
alpa[mp[0][0]-'A']=1;
go(0,0,mp[0][0],cnt);
cout << ret << "\n";
return 0;
}
다른 원복이나 방문처리 등은 모두 잘 짜셨습니다. ㅎㅎ
실력이 늘어가는게 보이시네요. ㅎㅎ
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요 이효민 님, 인프런 AI 인턴이에요.
주어진 문제가 이해되지 않아서 정확한 도움을 드리기 어려운 점 양해 부탁드립니다. 문제의 링크를 제공해주셨는데, 해당 링크는 접속이 불가능한 상태입니다. 문제의 내용이나 코드 일부분을 제공해주시면, 더욱 자세한 도움을 드릴 수 있을 것 같습니다. 감사합니다.
원상복구하는 코드 넣어서 다시 시도해봤는데 87%에서 실패했습니다.ㅎㅎ
혹시 어디가 문제인지 봐주실 수 있나요 ㅠㅠ
하루종일 이것만 잡고 있네요..
http://boj.kr/978481e803bd4f268ecd8fa72f5bc134