[파이썬, 자바] 백준 14867 : 물통 (골드2)

[파이썬, 자바] 백준 14867 : 물통 (골드2)

• https://www.acmicpc.net/problem/14867

---

풀이

방향성 생각

• 입력이 조금 크고 물통 A,B의 순서가 중요해서 시간이 조금 빡빡하다.
• 두 물통의 상태 변화를 파이썬에선 V에 tuple로 넣고,

 

---

파이썬

from collections import deque

def bfs(X,Y,ex,ey):
    Q = deque([(0,0,0)])
    V = set([(0,0)])

    while Q:
        cx,cy,t = Q.popleft()

        if (cx,cy) == (ex,ey):
            return t

        for nx,ny in [(X,cy),(cx,Y),(0,cy),(cx,0),
                    (min(cx+cy,X), max(0,cx+cy-X)),
                    (max(0,cx+cy-Y), min(cx+cy,Y))]:

            if (nx,ny) not in V:
                V.add((nx,ny))
                Q.append((nx,ny,t+1))
    return -1

X,Y,ex,ey = map(int,input().split())

result = bfs(X,Y,ex,ey)
print(result)

자바

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());
        int ex = Integer.parseInt(st.nextToken());
        int ey = Integer.parseInt(st.nextToken());

        System.out.println(bfs(X,Y,ex,ey));
    }

    public static int bfs(int X, int Y, int ex, int ey) {
        ArrayDeque<int[]> Q = new ArrayDeque<>();
        Q.offer(new int[] {0,0,0});
        Set<String> V = new HashSet<>();
        V.add("0,0");

        while (!Q.isEmpty()) {
            int[] cinfo = Q.poll();
            int cx = cinfo[0], cy = cinfo[1], t = cinfo[2];

            if (cx==ex && cy== ey) {
                return t;
            }

            int[][] nextStates = {
                {X,cy}, {cx,Y}, {0,cy}, {cx,0},
                {Math.min(cx+cy,X), Math.max(0,cx+cy-X)},
                {Math.max(0,cx+cy-Y), Math.min(cx+cy,Y)}
            };

            for (int[] ninfo : nextStates) {
                int nx = ninfo[0], ny = ninfo[1];
                String ninfoString = nx + "," + ny;
                if (!V.contains(ninfoString)) {
                    V.add(ninfoString);
                    Q.offer(new int[] {nx, ny, t+1});
                }
            }
        }
        return -1;
    }
}

• 자바에서는 튜플을 따로 정의하거나, 문자열로 바꿔서 방문체크한다.

---

코멘트

• 골4에 같은 문제가 있었던 거로 기억...
• 변수명 최적화가 좀 필요하다.
  • 시작은 start -> sx,sy
  • 끝은 end -> ex,ey
  • 현재노드는 cur -> cx,cy
  • 이전 노드는 prev -> px,py
  • 다음 노드는 nxt -> nx,ny
  • 테스트 케이스는 TC -> tc
  • 등등 최대한 x,y,i,j랑 안겹치게 하고, p,q,t,d 등 자주 쓰는 변수들도 안겹치게하기.