Baekjoon 9205번 맥주 마시면서 걸어가기

문제

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

걸린 시간

01 : 20 : 54

풀이

Python3

def dfs():
    s = []
    s.append(house)
    visited = [False]*len(store)
    dx, dy = dest

    while s:
        x, y = s.pop()

        if abs(dx-x)+abs(dy-y) <= 50*20:
            return "happy"

        for i in range(0, len(store)):
            if not visited[i]:
                sx, sy = store[i]
                if abs(sx-x)+abs(sy-y) <= 50*20:
                    visited[i] = True
                    s.append(store[i])

    return "sad"

if __name__ == "__main__":
    t = int(input())

    result = []

    for _ in range(0, t):
        n = int(input())

        # 좌표 입력
        house = list(map(int, input().split()))

        store = []
        for _ in range(0, n):
            store.append(list(map(int, input().split())))

        dest = list(map(int, input().split()))

        result.append(dfs())    

    for i in result:
        print(i)

문제를 한 시간 정도 잡고 있을 때쯤, 생각해본 경우의 수가 너무나도 많아 뭔가 잘못된 방법으로 풀이하고 있다는 걸 알아차렸다.

모든 경우의 수를 한 번씩 테스트해볼 필요가 있다고 생각되어 한 경로를 모두 탐색하고 다음으로 넘어갈 수 있는 DFS 로 문제를 해결했다.

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n;
pair<int, int> src, dest;
vector<pair<int, int>> store(100);
int visited[100];

void bfs(){
    queue<pair<int, int>> q;
    q.push(src);
    int dx = dest.first;
    int dy = dest.second;
    while(!q.empty()){
        auto loc = q.front();
        int x = loc.first;
        int y = loc.second;
        q.pop();
        // 목적지에 도달 가능하면
        if(abs(dx-x)+abs(dy-y) <= 1000){
            cout << "happy\n";
            return;
        }
        for(int i = 0; i < n; i++){
            int sx = store[i].first;
            int sy = store[i].second;
            if(abs(sx-x)+abs(sy-y) <= 1000){
                if(!visited[i]){
                    visited[i] = 1;
                    q.push(store[i]);
                }
            }
        }
    }
    cout << "sad\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> n;
        cin >> src.first >> src.second;
        for(int i = 0; i < n; i++)
            cin >> store[i].first >> store[i].second;
        cin >> dest.first >> dest.second;
        memset(visited, 0, sizeof(visited));
        bfs();
    }
    return 0;
}

c++ 언어로 다시 풀어보았다. 큐를 스택으로만 바꾸면 DFS 가 되니 풀이 방법은 동일하다.

다시 푸는 문제지만 한번에 성공하지 못했다. 이유는 탐색 과정에서 입력받은 편의점의 개수가 아닌 좌표를 저장하는 배열의 최대 크기만큼 반복하는 실수를 했기 때문이다.