[파이썬, Java] 9205. 맥주 마시면서 걸어가기

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다. 

예제 입력 1 

2

2

0 0

1000 0

1000 1000

2000 1000

2

0 0

1000 0

2000 1000

2000 2000

예제 출력 1 

happy

sad

 

 

✨ 나의 풀이

import java.io.*;
import java.util.*;

class Node{
    int x;
    int y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}

class Main {
    static int n;
    static int[][] pos;
    static boolean[] visit;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());      // 테케 수
        for(int t=0; t<T; t++){
            n=Integer.parseInt(br.readLine());         // 편의점의 개수
            pos=new int[n+2][2];
            visit=new boolean[n+2];
            for(int i=0; i<n+2; i++){
                StringTokenizer st=new StringTokenizer(br.readLine());
                pos[i][0]=Integer.parseInt(st.nextToken());     // x좌표
                pos[i][1]=Integer.parseInt(st.nextToken());     // y좌표
            }
            bfs();
        }
    }

    public static void bfs(){
        Deque<Node> deque=new LinkedList<>();
        deque.add(new Node(pos[0][0], pos[0][1]));
        while(!deque.isEmpty()){
            Node node=deque.pollFirst();
            if(node.x == pos[n+1][0] && node.y == pos[n+1][1]){
                System.out.println("happy");
                return;
            }

            for(int i=1; i<=n+1; i++){
                if(!visit[i]){
                    if(Math.abs(node.x-pos[i][0])+Math.abs(node.y-pos[i][1]) <= 1000){
                        visit[i]=true;
                        deque.add(new Node(pos[i][0], pos[i][1]));

                    }
                }

            }
        }
        System.out.println("sad");
    }
}

BFS

다른 사람 풀이를 참고해서 완성했다.

현재 node의 좌표와 거리가 1000 이하로 차이가 나는 좌표를 찾아 deque에 추가한다.

 

 

# 실패
import sys
input=sys.stdin.readline
t=int(input())

for _ in range(t) :
    flag=True
    alchol = 20
    n=int(input())  # 편의점의 개수
    x, y = map(int, input().split())
    for i in range(n+1) :
        dx, dy=map(int, input().split())
        if not flag :
            continue
        distance=abs(dx-x)+abs(dy-y)
        need_alchol=distance//50
        if alchol < need_alchol :
            flag=False
        else :
            alchol=alchol-need_alchol+20
            x, y=dx,dy
    if flag :
        print("happy")
    else :
        print("sad")

n+2개만큼 입력 받으면서 로직을 실행했다.

다른 사람들의 풀이를 보니 DFS, BFS로 풀었다.

단순 구현 문제가 아니었군😅

아 생각해보니 입력이 오름차순으로 정렬되어 주어진다는 보장이 없구나

문제의 테케만 통과한 이유가 이것이었다.

 

 

🍟 다른 사람 풀이

# https://chldkato.tistory.com/44
from collections import deque
import sys

input=sys.stdin.readline

def bfs(x, y) :
    q, c=deque(), []
    q.append([x, y, 20])
    c.append([x, y, 20])
    while q :
        x, y, beer=q.popleft()
        if x == x1 and y == y1 :		# 도착
            print("happy")
            return
        for nx, ny in d :
            if [nx, ny, 20] not in c :
                l1=abs(nx-x)+abs(ny-y)		# 거리
                if beer*50 >= l1 :
                    q.append([nx, ny, 20])
                    c.append([nx, ny, 20])
    print("sad")
    return

tc=int(input())
while tc :
    n=int(input())
    x0, y0=map(int, input().split())	# 집 좌표
    d=[]
    for _ in range(n) :
        x, y=map(int, input().split())
        d.append([x, y])
    x1, y1=map(int, input().split())	# 도착 좌표
    d.append([x1, y1])	
    bfs(x0, y0)
    tc-=1

BFS

리스트 d에 편의점, 도착 좌표가 순차적으로 들어있다.

리스트 c는 방문기록이라고 할 수 있다.

if [nx, ny, 20] not in q로 할 경우 무한반복에 걸린다.

 

 

# https://pacific-ocean.tistory.com/395

import sys
input=sys.stdin.readline

def d() :
    for i in range(n+2) :
        for j in range(n+2) :
            if i == j : continue
            if abs(s[i][0]-s[j][0])+abs(s[i][1]-s[j][1]) <= 1000 :
                s_[i][j]=1
                s_[j][i]=1

def dfs(start) :
    visit[start]=1
    for i in range(n+2) :
        if s_[start][i] == 1 and visit[i] == 0 :
            dfs(i)
t=int(input())
for i in range(t) :
    n=int(input())
    s=[list(map(int, input().split())) for i in range(n+2)]
    s_=[[0]*(n+2) for i in range(n+2)]		# 연결정보
    visit=[0 for i in range(n+2)]
    d()
    dfs(0)
    if visit[n+1] == 1 : print("happy")
    else : print("sad")

DFS 

d 함수에서 i와 j의 거리가 1000이하면 양방향 연결을 한다.

visit[n+1]은 도착지의 방문여부다.

 

 

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException{
        new Main().run();
    }

    int N;
    boolean[] visit;
    int[][] store;
    int px=0, py=0;
    public void run() throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer token=null;
        int hx=0, hy=0;

        int T=Integer.parseInt(in.readLine().trim());

        flag:for(int t=0; t<T; t++){
            N=Integer.parseInt(in.readLine().trim());
            visit=new boolean[N];
            store=new int[N][2];
            token=new StringTokenizer(in.readLine().trim());
            hx=Integer.parseInt(token.nextToken());
            hy=Integer.parseInt(token.nextToken());

            for(int i=0; i<N; i++){
                token=new StringTokenizer(in.readLine().trim());
                store[i][0]=Integer.parseInt(token.nextToken());
                store[i][1]=Integer.parseInt(token.nextToken());
            }
            token=new StringTokenizer(in.readLine().trim());
            px=Integer.parseInt(token.nextToken());
            py=Integer.parseInt(token.nextToken());
			
            if(Math.abs(px-hx)+Math.abs(py-hy) >1000*(N+1)){ 
                out.write("sad\n");
                continue;
            }
        Arrays.fill(visit, false);
        isHappy=false;
        dfs(hx, hy);
        if(isHappy){
            out.write("happy\n");
        }else{
            out.write("sad\n");
        }
        }
        out.flush();
        out.close();
    }

    public boolean isNear(int px, int py, int hx, int hy){
        return Math.abs(px-hx)+Math.abs(py-hy) <= 1000;
    }

    boolean isHappy;
    public void dfs(int currX, int currY){
        if(isNear(px, py, currX, currY)){
            isHappy=true;
            return;
        }

        for(int i=0; i<N; i++){
            if(!visit[i] && isNear(store[i][0], store[i][1], currX, currY)){
                visit[i]=true;
                dfs(store[i][0], store[i][1]);
            }
        }
    }
}

DFS

BufferedWriter에 넣고 한꺼번에 출력해서 효율을 높인다.

if(Math.abs(px-hx)+Math.abs(py-hy) >1000*(N+1)){
	out.write("sad\n");
	continue;
}

입력 받은 값이 계산해봤자 sad가 나올 것 같으면 미리 처리한다.

 

 

import java.io.*;
import java.util.*;

class Main {
    static boolean found;
    static class Node{
        int x;
        int y;

        public Node(int x, int y){
            this.x=x;
            this.y=y;
        }
    }
    static Node[] places;
    static StringBuilder sb;
    static int N;
    static boolean[] visited;
    static Queue<Integer> queue;

    public static boolean possibleDist(int curPlace, int destPlace){
        if(Math.abs(places[curPlace].x - places[destPlace].x)+Math.abs(places[curPlace].y-places[destPlace].y) > 1000){
            return false;
        }else
            return true;
    }

    public static void bfs(){
        while(!queue.isEmpty()){
            int curPlace=queue.poll();      // 현재 위치
            if(curPlace == N+1){
                found=true;
                break;
            }
            for(int i=N+1; i>=1; i--){
                if(!visited[i] && possibleDist(curPlace, i)){
                    visited[i]=true;
                    queue.offer(i);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        sb=new StringBuilder("");
        StringTokenizer st;
        for(int t=0; t<T; t++){
            queue=new LinkedList<>();
            found=false;
            N=Integer.parseInt(br.readLine());
            visited=new boolean[N+2];
            places=new Node[N+2];
            // 상근 집, 편의점, 락페
            for(int i=0; i<N+2; i++){
                st=new StringTokenizer(br.readLine());
                places[i]=new Node(Integer.parseInt(st.nextToken()),
                        Integer.parseInt(st.nextToken()));
            }
            visited[0]=true;
            queue.offer(0);     // 출발점
            bfs();
            if(found)
                sb.append("happy").append("\n");
            else
                sb.append("sad").append("\n");
        }
        System.out.println(sb);
    }
}

BFS

N+1에서 1까지 for문을 돌리면서 거리가 1000이내인 i를 찾는다.

StringBuilder에 넣고 한번에 출력한다.

 

 

문제 출처 👉 백준