[백준/c++]14503

https://www.acmicpc.net/problem/14503

https://velog.io/@sj-lee33/%EB%B0%B1%EC%A4%80-14503%EB%B2%88-%EB%A1%9C%EB%B4%87-%EC%B2%AD%EC%86%8C%EA%B8%B0-c-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%92%80%EC%9D%B4

위 블로그를 풀이를 이용했습니다.

BFS 와 DFS

그래프의 모든 정점을 방문해야 하는 경우 -> BFS, DFS 둘 다 가능

경로의 특징을 저장해둬야 하는 문제 -> DFS

최단거리 구해야 하는 문제 -> BFS

(출처: https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90)

해당 문제는 후진을 해야하므로 DFS를 사용하는 것이 좋을 것 같습니다.

DFS를 사용한 문제 풀이를 조사했고 토대로 공부했습니다.

#include <iostream>
using namespace std;

int n,m,r,c,d;
int map[50][50];

int visited[50][50];
int visited_count={0,};

//북(0) 동(1) 남(2) 서(3)
//세로축 x , 가로축 y
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

void dfs(){
    
    //4방향으로 탐색
    for(int i=0;i<4;i++){
        //왼쪽 방향으로만 회전하므로
        // 북:0 동:1 남:2 서:3
        // 북(0)->서(3) 서(1)->남(0) 남(2)->동(1) 동(3)->북(2)
        int next_d = (d + 3 - i) % 4;
        int next_r=r+dx[next_d];
        int next_c=c+dy[next_d];

        // 2.왼쪽방향에 청소할 공간이 없다면 그 방향으로 회전하고 2번으로 돌아간다 
        // 다음 위치가 범위내에 있는지 확인하고 map에서 청소할 수 있는 공간인지 확인한다
        // 1이면 청소할 수 없는 공간이므로 넘어감
        // continue 는 아래문을 무시하고 조건으로 넘어감
        if(next_r < 0 || next_r >=n || next_c < 0 || next_c >= m || map[next_r][next_c]){
            continue;
        }

        // 1.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행
        // map에서 0이고 방문하지 않았을 경우는 아직 청소하지 않은 공간임
        if(map[next_r][next_c]==0 && visited[next_r][next_c]!=1){
            // 방문기록 해주고 청소했으므로 카운트 올려줌
            visited[next_r][next_c]=1;
            visited_count++;
            // 위치가 이동되었으므로 좌표값 다시 설정해줌
            // *** 이때 방향도 꼭 같이 설정해주어야함 !!!! -> 내가 실수했기 때문에 중요표시 ***
            r=next_r; 
            c=next_c;
            d=next_d; //***다음방향정해주는거 잊지말기***
            dfs();
        }
        
    }

    //3,4 4방향 모두 청소가 된 경우

    //후진 방향 설정
    // 북(0) -> 남(2) , 동(1) -> 서(3) , 남(2) -> 북(0) , 서(3) -> 동(1)
    int back_idx= d > 1 ? d-2 : d+2;  
    int back_r = r + dx[back_idx];
    int back_c = c + dy[back_idx];

    //후진하는 좌표가 범위 내 인지 확인
    if((back_r >= 0 && back_r <= n) || (back_c >= 0 && back_c <= m)){
        // 3.후진가능한 경우
        // map 에서 0 이면 후진 가능한 경우이므로 후진해준다.
        if(map[back_r][back_c] == 0){
            r=back_r;
            c=back_c;
            dfs();
        }
        else{ 
            // 4. 후진 안되는 경우
            // 후진 안되면 dfs 종료하고 결과 출력해주면 된다.
            cout << visited_count ;
            exit(0);
        }
    }

}

int main(){
    ios::sync_with_stdio;
    cin.tie(0);

    cin >> n >> m >> r >> c >> d;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> map[i][j];
        }
    }

    //*** 현재 위치도 청소해주는 것 명심 ***
    visited[r][c] =1;
    visited_count++;
    dfs();

}