백준 [java 자바] 2251번 : 물통

 문제를 보고 처음 계획을 세울 때 감이 잘 잡히지 않았던 문제이다. 

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

class three {
	
	int a;
	int b;
	int c;
	
	three(int a, int b, int c){
		this.a = a;
		this.b = b;
		this.c = c;
	}
	
}


class Main{
	
	
   
	
 public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st  = new StringTokenizer(br.readLine());
    StringBuilder sb = new StringBuilder();
    
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());
    
    boolean[][][] vis = new boolean[a+1][b+1][c+1];
    int[] arr = new int[c+1];
   
    
    Stack<three> stack = new Stack<>();
    
    stack.push(new three(0,0,c));
    
    while(stack.isEmpty() != true) {
    	three n = stack.pop();
    	int na = n.a;
    	int nb = n.b;
    	int nc = n.c;
    	vis[na][nb][nc] = true;
    	if(na == 0) arr[nc] = 1;
      
    	
    	if(na<a) {
    		if(nb>0) {//b-a
    			if(na+nb>a) {
    				if(!(a ==0 && na+nb-a == 0) && vis[a][na+nb-a][nc] == false) stack.push(new three(a,(na+nb)-a,nc));
    			}
    			else {
    				if(na+nb != 0 && vis[na+nb][0][nc] == false)stack.push(new three(na+nb,0,nc));
    			}
    		}
    		if(nc>0) {//c-a
    			if(na+nc>a) {
    				if(vis[a][nb][nc+na-a] == false) stack.push(new three(a,nb,nc+na-a));
    			}
    			else {
    				if(vis[na+nc][nb][0] == false) stack.push(new three(na+nc,nb,0));
    			}
    		}
    	}
    	if(nc<c) {
    		if(nb>0) {//b-c
    			if(nc+nb>c) {
    				
    			}
    			else {
    				if(na !=0 && vis[na][0][nc+nb] == false)stack.push(new three(na,0,nc+nb));
    			}
    		}
    		if(na>0) {//a-c
    			if(nc+na>c) {
    				
    			}
    			else {
    				if(na !=0 && vis[0][nb][nc+na] == false)stack.push(new three(0,nb,nc+na));
    			}
    		}
    	}
    	if(nb<b) {
    		if(na>0) {//a-b
    			if(na+nb>b) {
    				if(na+nb-b !=0 && vis[na+nb-b][b][nc] == false) stack.push(new three(na+nb-b,b,nc));
    			}
    			else {
    				if(na+nb != 0&& vis[0][na+nb][nc] == false) stack.push(new three(0,nb+na,nc));
    			}
    		}
    		if(nc>0) {//c-b
    			if(nc+nb>b) {
    				if(na !=0 && vis[na][b][nc+nb-b] == false) stack.push(new three(na,b,nc+nb-b));
    			}
    			else {
    				if(vis[na][nb+nc][0] == false)stack.push(new three(na,nb+nc,0));
    			}
    		}
    	}
    }
    
    for(int i = 0;i<=c;i++) {
    	if(arr[i] == 1) sb.append(i).append(" ");
    }
    
    System.out.println(sb);
    
    
   
    
 }

 }

 three라는 클래스를 만들고 스택에 class단위로 저장해두었다. 그리고 하나하나 꺼내며 모든 경우를 다 해보고 결괏값을 스택에 집어넣는다. 처음에는 저절로 스택이 빌 것이라고 생각했는데 주고받고 하면 무한대로 코드가 돈다. 그래서 삼차원 배열을 이용하여 방문 여부를 저장하였다. 

스택에서 꺼낸 값의 a값이 0일때만 해당 c값에 (arr의) 1을 대입해주었고 반복문을 이용해 출력하였다.

 

알아야 할 점 :
1. 방문여부를 체크할 때 삼차원 배열도 사용 가능하다. 

 

다른 사람 코드와 다른 점 :

 int [] from = {0, 0, 1, 1, 2, 2}; 

        int [] to = {1, 2, 0, 2, 0, 1};

이렇게 하고 무조건 더해주고 그 다음 넘치는지 여부를 보고 답을 구했다.

그리고 합은 항상 일정하므로 두개만 저장하고 나머지는 빼서 구했다.