안녕하세요! 친구가 맛있는 초밥을 사줘서 기분이 참 좋은 GCOCO입니다!😀

반갑습니다 선생님들. 4월22일 오늘, 날씨가 굉장히 좋았다는 사실을 알고계셨나요?
숨은 고수님들은 집에서 또 코딩하시느라 못보셨을수도 있겠지만...
아무튼! 날씨가 굉장히 좋아서 친구와 밥을 먹고 롤도하고!
운동을 마치고 길을 따라 자전거를 타고 오는데 어느새 피워낸 봄 꽃과 사람의 조화가 어찌나 아름답던지.
절로 기분이 좋아지는 하루였습니다.

오늘의 문제는 이것입니다!

문제링크:

참고로 오늘의 문제에 전 패배하였기에, 해당 코드는 CHAT GPT의 도움을 받아 작성된 코드입니다.

제가 처음 작성한 코드는 다음과 같습니다!

#include<vector>
using namespace std;
bool dfs(vector<vector<int>> &maps,int row, int col, int now,int &answer,vector<vector<bool>> &visited,int *dx,int *dy){

    if(row==visited.size()-1&&col==visited[0].size()-1){
        if(answer<now)
            answer = now;
        return true;
    }
    
    for(int i=row;0<=i&&i<visited.size();i++){
        for(int j=col;0<=j&&j<visited[0].size();j++){
            if(!visited[i][j]&&maps[i][j]){
                visited[i][j]=true;
                for(int k=0;k<4;k++){
                    bool ret = dfs(maps,row+dx[k],col+dy[k],now+1,answer,visited,dx,dy);
                    if(ret)
                        return true;
                }
                visited[i][j]=false;
            }
        }
    }
    return false;
}

int solution(vector<vector<int> > maps)
{
    vector<vector<bool>> visited(maps.size(),vector<bool>(maps[0].size(),false));    
    int answer=-1;
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,1,-1};
    dfs(maps,0,0,0,answer,visited,dx,dy);
    return answer;
}

완전탐색이란 태그를 보고, dfs의 개념을 사용해 문제를 풀어보려고 시도하였습니다!
허나 dfs함수를 보시다싶이, 제대로 된 코드라고 볼 수 없습니다.
이유를 차근차근 뜯어보면

if(row==visited.size()-1&&col==visited[0].size()-1){
        if(answer<now)
            answer = now;
        return true;
}

우선 이 부분의 answer 설정 조건이 잘못됨을 알 수 있습니다.
우리가 answer로 찾아야 할 값은, now의 max값이 아닌, min값입니다!

for(int i=row;0<=i&&i<visited.size();i++){
        for(int j=col;0<=j&&j<visited[0].size();j++){
            if(!visited[i][j]&&maps[i][j]){
                visited[i][j]=true;
                for(int k=0;k<4;k++){
                    bool ret = dfs(maps,row+dx[k],col+dy[k],now+1,answer,visited,dx,dy);
                    if(ret)
                        return true;
                }
                visited[i][j]=false;
            }
        }
}
return false;

또한 탐색을 하는 부분도 문제가 있음을 알 수 있습니다. 의도는 모든 부분을 탐색하며 돌고싶지만 제가 작성한 코드는 제대로 된 탐색을 실행하고 있지 않죠. 실제로 코드를 돌려보면 의도대로 작동하지 않습니다. 아래는 GPT의 피드백을 받은 DFS 코드입니다.

#include<vector>
using namespace std;
bool dfs(vector<vector<int>> &maps,int row, int col, int now,int &answer,vector<vector<bool>> &visited,int *dx,int *dy){
    //범위를 탈출하는 경우 false;
    if(row < 0 || row >= maps.size() || col < 0 || col >= maps[0].size() 
       || visited[row][col] || !maps[row][col]){
        return false;
    }
    //종착점 도착시 
    if(row==visited.size()-1&&col==visited[0].size()-1){
        if(answer == -1||answer > now)
            answer = now;
        return true;
    }
    
    //현재지점 방문 표시
    visited[row][col] = true;
    //상 하 좌 우 탐색
    for(int k=0;k<4;k++){
        dfs(maps, row+dx[k], col+dy[k], now+1, answer, visited, dx, dy);
    }
    //visited 다시 복구해주기
    visited[row][col] = false;
    
    
    return false;
}

int solution(vector<vector<int> > maps)
{
    vector<vector<bool>> visited(maps.size(),vector<bool>(maps[0].size(),false));    
    int answer=-1;
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,1,-1};
    dfs(maps,0,0,1,answer,visited,dx,dy);
    return answer;
}

역시 GPT. 상당히 코드가 깔끔함을 느낄수 있었습니다.
제 코드와 비교해보자면 다음과 같습니다.

1. 범위를 탈출하는 경우를 확실히 설정하였다.
2. 종착점의 도착시 종료조건을 확실히 해주었다.
3. 현재 지점의 방문을 표시해주고, 상 하 좌 우를 탐색을 실시하고 다시 복구하였다.

제가 깨달음을 얻었던 부분은 다음입니다.

	visited[row][col] = true;
    //상 하 좌 우 탐색
    for(int k=0;k<4;k++){
        dfs(maps, row+dx[k], col+dy[k], now+1, answer, visited, dx, dy);
    }
    //visited 다시 복구해주기
    visited[row][col] = false;

제가 원했던 탐색은 바로 위의 코드였던것입니다!
하지만 저의 실력부족으로 인해 제대로 된 코드를 작성하지 못했던 것이었죠.
GPT에게 또 한번 배워가는 부분이었습니다.

그리고서 문제를 제출했지만 틀렸습니다.
바로 이 문제는 DFS의 개념을 사용하는 문제가 아니었습니다!
DFS를 사용하였기에 최단거리를 계산하는 문제이지만 불필요한 연산이 너무 많아 효율성 테스트를 통과하지 못했던 것이었죠.

하지만 BFS를 사용해서 문제를 풀어본 경험이 없는 저는, 이참에 GPT에게 배워보기로 했습니다!

Hey GPT. BFS로 푼 코드 알려줘!

#include<vector>
#include <queue>
using namespace std;

int solution(vector<vector<int> > maps)
{
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    
    int n = maps.size();
    int m = maps[0].size();
    
    queue<pair<int,int>> q;
    q.push(make_pair(0,0));
    
    vector<vector<int>> dist(n,vector<int>(m,-1));//거리를 저장할 vector
    dist[0][0] = 1;//시작점의 거리값을 1로 초기화
    while(!q.empty()){
    	//현재 지점의 x,y값 저장
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i=0;i<4;i++){
        	//상 하 좌 우 탐색
            int nx = x + dx[i];
            int ny = y + dy[i];
            //범위내의 값이라면 
            if(0<=nx && nx<n && 0<=ny && ny<m){
            	//갈 수 있는 지형이고, 아직 방문하지 않은 곳이라면
                if(maps[nx][ny] && dist[nx][ny]==-1){
                	//해당 지점까지의 거리 계산
                    dist[nx][ny] = dist[x][y]+1;
                    //해당 지점에서의 탐색을 위해 queue에 삽입
                    q.push(make_pair(nx,ny));
                }
            }
        }
    }
    //마지막 지점에서의 거리값 반환(도착하지 못할시 default값인 -1 반환)
    return dist[n-1][m-1];
}

★우리는 GPT의 시대에 살고있다★

코드를 보고 경악을 금치 못하였습니다. 이렇게나 잘 짜여진 코드라니....
GPT가 없던 시절엔 혼자 낑낑 앓면서 결국 문제도 풀지 못하고 포기하는 경우가 아주 많은 경우가 있었습니다. 괴로운 시절이었습니다. 하지만 이젠 모르는 개념이나 문제를 GPT를 통해
"아주 효율적인 코드로" 배울수있다니 굉장히 기쁩니다!

제가 단 주석과 함께 코드를 분석해보겠습니다!

1. n x m 사이즈를 측정한다.
2. queue<pair<int,int>> q를 이용하여 탐색을 할 예정
3. 초기 시작값인 (0,0) 삽입
4. 거리를 저장할 vector dist를 선언
5. while문을 이용하여 q가 빌때까지 탐색 실시.(마지막 지점 도착시 종료)
6. x,y를 이용해 현재 지점의 위치 변수에 저장, q에서 방출
7. for문을 이용해 상 하 좌우 탐색
8. 갈 수 있는 지형이고, 아직 방문하지 않은 곳이라면 해당 지점까지의 거리 계산
9. 또한 해당 지점에서의 탐색을 위해 queue에 삽입
10. 마지막 지점에서의 거리값 반환(도착하지 못할시 default값인 -1 반환)

너무 감동적인 코드입니다. 지식이 또 늘었습니다!
그렇지만, 단순히 코드의 흐름만 알 것이 아닌 DFS와 BFS의 개념을 다시 잡을 필요가 있다고 느꼈습니다.
내일은 DFS와 BFS관한 포스팅을 해보도록 하겠습니다!