[백준 16724번] 피리 부는 사나이

아이디어

맨처음엔 visited를 bool타입으로만 풀려고해서 한번 실패하고, 백트래킹 해두고 visited를 다른 숫자로 바꾸는 방식으로 해서 차이를 두려고 했더니 시간초과가 나서

아예 매 bfs마다 다른숫자를 사용하는 것으로 고쳤다.

 

기존 문제점

첫 bfs일 때 모습

 

두번째 bfs 모습

위에꺼 처럼 visited true로만 처리하게 되면 아래 그림에서 2,3,4일때 visited true인걸 계속 만나서 count가 증가하기 때문에 구분해줬다.

 

C++  풀이

#include <bits/stdc++.h>
using namespace std;
int N,M;
int board[1000][1000];
int visited[1000][1000];
int dx[4] = {-1, 0 , 1 , 0}; // U, R, D , L;
int dy[4] = {0, 1, 0, -1 };
queue<pair<int,int>> q;
int cnt = 0;

void bfs(int x, int y,int check)
{
    visited[x][y] = check; // bfs가 실행될 때 마다 check가 1씩증가해서 들어옴.
    q.push({x,y});
    while(!q.empty())
    {
        int px = q.front().first; //기존 위치
        int py = q.front().second;//기존 위치
        int nx = px+ dx[board[px][py]]; // direction 참조해서 바뀐위치.
        int ny = py+ dy[board[px][py]]; // direction 참조해서 바뀐위치.
        q.pop();
        if(visited[nx][ny] == 0) // 한번도 안가본 곳이라면.
        {
            visited[nx][ny] = check; //check해주고 q에 push함.
            q.push({nx,ny});
        }
        else if(visited[nx][ny] == check){ //가본 곳에 다시 왔다면 싸이클이 생긴것.
            cnt++; // 출력개수를 증가시키고
            while(!q.empty()) q.pop(); //global 변수라 다음 bfs에 사용하려고 q를 비워주고 종료.
            return;
        }
        //이번 bfs때 들어온게 아니라면 이전에 싸이클 확인을 했기에 출력개수 증가 안시킴.
        else if(visited[nx][ny] != check){ 
            while(!q.empty()) q.pop();
            return;
        }
    }
}
int main(void)
{
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for(int i = 0 ; i< N; i++)
    {
        for(int j = 0 ; j< M; j++)
        {
            char c;
            cin >> c;
            //각 direction을 dx, dy배열에서 참조하기 위해서 숫자로 바꿨음.
            if(c == 'U') board[i][j] = 0;
            else if(c == 'R') board[i][j] = 1;
            else if(c == 'D') board[i][j] =2 ;
            else board[i][j] = 3;
        }
    }    
    int check=1;
    for(int i = 0 ; i< N; i++)
    {
        for(int j = 0 ; j< M; j++)
        {
            if(visited[i][j]==false)
            {
                bfs(i, j,check);
                check++;
            }
        }
    }
    cout << cnt << endl;
}