레이저 통신

 

BFS문제, 시뮬레이션으로도 풀수있을것 같긴한데, 그냥 끝까지가서 BFS 하면되는문제

 

까다로운점은 이제 한 직선내에서 모든점들에 대해 BFS를 하다보면, 중복되는지점(방문한 지점)에서 더 작은 값의대한처리는 어떻게 할지 이다.

#include<iostream>
#include<queue>
#include<utility>

using namespace std;

int r,c;
char map[100][100];
int dist[100][100];
bool visit[100][100];
int dx[] ={0,0,1,-1};
int dy[] = {1,-1,0,0};
int ans = 0;

void bfs(int x, int y){
    queue<pair<int,int>> q;
    visit[x][y] = true;
    q.push({x,y});
    while(!q.empty()){
        x= q.front().first; y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x+dx[i]; int ny = y+dy[i];
            while(true){
                if(nx >= 0 && nx < r &&ny>=0 &&ny<c) {
                    if (map[nx][ny] != '*' && visit[nx][ny] == false) {

                        visit[nx][ny] = true;
                        q.push({nx, ny});
                        dist[nx][ny] = dist[x][y] + 1;
                        if (map[nx][ny] == 'C') ans = dist[nx][ny];
                        nx += dx[i];
                        ny += dy[i];
                        /*else if(visit[nx][ny] == true){
                            if(dist[nx][ny] > dist[x][y] +1){
                                dist[nx][ny] = dist[x][y]+1;
                                if (map[nx][ny] == 'C') ans = dist[nx][ny];
                                q.push({nx, ny});
                                nx += dx[i];
                                ny += dy[i];

                            }
                        }*/
                    } else if(map[nx][ny] != '*' && visit[nx][ny] == true
                    && dist[nx][ny] >= dist[x][y]+1){
                        q.push({nx, ny});
                        dist[nx][ny] = dist[x][y] + 1;
                        if (map[nx][ny] == 'C') ans = dist[nx][ny];
                        nx += dx[i];
                        ny += dy[i];
                    }
                    else break;
                }
                else break;
            }
        }
    }

}

int main(){
    cin >>c>>r;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin>>map[i][j];
        }
    }
    for(int i = 0; i < r ; i++){
        for(int j = 0; j < c; j++){
            if(map[i][j] =='C' &&visit[i][j] == false) {
                bfs(i, j);
                break;
            }

        }
    }

    cout<<ans-1<<'\n';
    return 0;
}

 

까다로운 조건이라고 생각했지만, 그냥 더 작은값의 조건을 추가해서 넣어주면된다. 처음 설계시에 의아했던게, 오히려 디버깅하면서 확신이되었던문제