[백준] 16937 두 스티커 - 완전탐색 + 아이디어 JAVA

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

16937번: 두 스티커

문제풀이

완전탐색 문제  + DFS + 아이디어 가 사용된 문제입니다.

 

문제푸는 방식입니다.

1. 문제를 보면 주어진 스티커를 90도로 회전하는 경우가 있습니다. 이를 고려하여 처음부터 스티커를 Node에 같이 넣어줍니다. 이떄 스티커 값을 넣을떄 주어진 그대로의 정보(Ri, Ci, 스티커 Index) 를 넣고, 90도 회전한 정보에 (Ci, Ri, 스티커 Index)를 넣습니다. 이떄 스티커 Index를 넣어주어야 이후에 완전탐색을 통해 모든 경우를 조사할때 같은 스티커를 같이 검사하지 않습니다.

2. 주어진 스티커 중 최대 2개의 스티커만 뽑아서 최대의 넓이를 구하기 위해 DFS를 활용하여 완전탐색을 진행합니다. 이 과정에서 1번과정에서 넣어준 StickerIndex를 사용하여 방문처리하여, 같은 스티커를 2번 뽑아서 사용하는 일이 없도록 합니다. 또한 선택된 스티커는 SelectedSticker[level]을 활용하여 SelectedSticker[0], SelectedSticker[1] 로써 관리합니다.

3. 만약 Level == 2 라면, 최대길이를 구하기 위해 

         3.1 가로로 배치한경우 ( 가로길이는 W보다 작거나 같고, 세로길이는 두개의 SelectedSticker[0], SelectedSticker[1] 중 최대의 높이만 H 보다 작거나 같으면 됩니다. ) 그리고서 스티커의 넓이는 구해서 더합니다.

         3.2 세로로 배치한경우 ( 세로길이는 H보다 작거나 같고, rkfh길이는 두개의 SelectedSticker[0], SelectedSticker[1] 중 최대의 가로만 W 보다 작거나 같으면 됩니다. ) 그리고서 스티커의 넓이는 구해서 더합니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
	public static int H, W;
	public static int N;
	public static ArrayList<Node> Node = new ArrayList<Node>();
	public static boolean[] visited;
	public static Node[] SelectedSticker = new Node[2]; //2개의 선택된 스티커 사용
	public static int result = 0;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	H = Integer.parseInt(st.nextToken()); 
    	W = Integer.parseInt(st.nextToken());
    	
    	
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	visited = new boolean[N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
        	int R = Integer.parseInt(st.nextToken());
        	int C = Integer.parseInt(st.nextToken());
        	Node.add(new Node(R, C, i));
        	if( R != C) {	//90도 회전까지 넣습니다.
        		Node.add(new Node(C, R, i));
        	}
    	}
    	
    	simulate(0, 0);
    	
    	System.out.println(result);
    }
    
    public static void simulate(int idx, int level) {
    	if(level == 2) {
    		//가로로 배치할때 ( 세로길이는 Sticker중 가장 긴것만 고려합니다. )
    		if(SelectedSticker[0].c + SelectedSticker[1].c <= W && Math.max(SelectedSticker[0].r, SelectedSticker[1].r) <= H) {
    			result = Math.max(result,  SelectedSticker[0].r * SelectedSticker[0].c + SelectedSticker[1].r * SelectedSticker[1].c);
    		}
    		//세로로 배치할때 ( 가로길이는 Sticker중 가장 긴것만 고려합니다. )
    		if(SelectedSticker[0].r + SelectedSticker[1].r <= H && Math.max(SelectedSticker[0].c, SelectedSticker[1].c) <= W)  {
    			result = Math.max(result,  SelectedSticker[0].r * SelectedSticker[0].c + SelectedSticker[1].r * SelectedSticker[1].c);
    		}
    		
    		return ;
    	}
    	
    	
    	for(int i=idx;i<Node.size();i++) {
    		Node temp = Node.get(i);
    		int R = temp.r;
    		int W = temp.c;
    		int TEMPSTICKERINDEX = temp.stickerIndex;  
    		if(visited[TEMPSTICKERINDEX] == true) continue; //중복된 스티커가 사용되지 않도록 처리합니다.
    		visited[TEMPSTICKERINDEX] = true;
    		SelectedSticker[level] = temp;  //Sticker의 순서에 맞춰 넣습니다.
    		simulate(i + 1,level + 1);
    		SelectedSticker[level] = null; //Sticker를 사용햇다면 제거합니다.
    		visited[TEMPSTICKERINDEX] = false;
    	}
    	
    }
}

class Node{
	int r;
	int c;
	int stickerIndex;
	public Node(int r, int c, int stickerIndex) {
		this.r = r;
		this.c = c;
		this.stickerIndex = stickerIndex;
	}
}