[백준/Baekjoon] 1445 일요일 아침의 데이트 C++ :: Dijkstra & Graph

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

1445번: 일요일 아침의 데이트

---

1. Logic

다른 분들의 풀이를 본 결과 내가 푼 방식인 위치마다 주위의 쓰레기 여부를 판단하는 방법이 있고 먼저 쓰레기 여부를 판단하여 배열에 넣은 후 다익스트라를 돌리는 방법 이렇게 2가지가 가장 대표적인 풀이인 것 같다.

내가 푼 방식인 위치를 옮길 때 마다 쓰레기 여부를 판단하는 방법은 

1. 입력을 받고 시작, 도착 위치를 기록 후

2. 다익스트라를 실행 하면서 내가 갈 위치(graph[ny][nx])가 쓰레기 인 경우  onTrash+1해서 queue에 넣어주고 만약 .(쓰레기가 없는 곳)이라면 .에서 다시한번 주변 4방향 체크를 해서 만약 쓰레기가 있다면 betweenTrash+1을 해서 pq에 넣어준다.

3. 목적지에 도착했다면 반복문을 빠져나와 출력해준다.

 

코드 상 변수

onTrash : 다익을 돌며 확인 한 현재 위치까지 쓰레기 있는곳을 직접적으로 지나온 횟수

betweenTrash : 다익을 돌며 확인 한 현재 위치까지 쓰레기 있는곳 주변을 지나온 횟수

 

//출력해야 할 값 : 우선순위 큐를 greater붙혀서 넣었기 때문에 항상 작은 값이 우선적으로 나온다.

onTrashCnt : 직접적으로 쓰레기 있는 곳을 지나온 최소 횟수

betweenTrashCnt : 쓰게기 있는 곳 주변을 지나온 최소 횟수

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n, m;

int sx, sy;
int fx, fy;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

char graph[51][51];
int dist[51][51];

void dijkstra() {
    priority_queue<pair<pair<int, int>, pair<int, int>>, vector<pair<pair<int, int>, pair<int, int>>>, greater<pair<pair<int, int>, pair<int, int>>>> pq;
    
    int onTrashCnt = 0;
    int betweenTrashCnt = 0;
    
    pq.push({{0, 0}, {sy, sx}});
    memset(dist, -1, sizeof(dist));
    
    dist[sy][sx] = 0;
    
    while(!pq.empty()) {
        int findCheck = false;
        
        int onTrash = pq.top().first.first;
        int betweenTrash = pq.top().first.second;
        int y = pq.top().second.first;
        int x = pq.top().second.second;
        
        pq.pop();
        
        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(ny == fy && nx == fx) {
                onTrashCnt = onTrash;
                betweenTrashCnt = betweenTrash;
                findCheck = true;
                break;
            }
            
            if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if(dist[ny][nx] != -1) continue;
            
            if(graph[ny][nx] == 'g') {
                pq.push({{onTrash+1, betweenTrash}, {ny, nx}});
            }
            else if(graph[ny][nx] == '.') {
                bool trashCheck = false;
                for(int j = 0; j < 4; j++) {
                    if(graph[ny+dy[j]][nx + dx[j]] == 'g') {
                        trashCheck = true;
                        break;
                    }
                }
                if(trashCheck) pq.push({{onTrash, betweenTrash+1}, {ny, nx}});
                else pq.push({{onTrash, betweenTrash}, {ny, nx}});
            }
            
            dist[ny][nx] = dist[y][x] + 1;
        }
        if(findCheck) break;
    }
    
    cout << onTrashCnt << " " << betweenTrashCnt;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> graph[i][j];
            
            if (graph[i][j] == 'S') {
				sy = i;
				sx = j;
			}
			else if (graph[i][j] == 'F') {
				fy = i;
				fx = j;
			}
        }
    }
    
    dijkstra();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐