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

 

14620번: 꽃길

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므

www.acmicpc.net

문제풀이

완전탐색 문제입니다.

각 꽃의 방문처리를 visited로 진행하면서 모든 경우의 수를 방문하면됩니다.

 

문제조건에

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

O(N^3) 의 시간복잡도를 가지지만 N이 10 이기에 완전탐색이 가능합니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	
	public static String T;
	public static int N;
	public static int[][] map;
	public static boolean[][] visited;
	public static int result = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	map = new int[N][N];
    	visited = new boolean[N][N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken()); 
    		}
    	}
    
        simulate(0, 0); 
    	
		System.out.println(result);
    	
 
    }
    
    public static void simulate(int level, int total) {
    	if(level == 3) {
    		result = Math.min(result,  total);
    		return ;
    	}
    	
    	for(int i=1;i<N-1;i++) {
    		for(int j=1;j<N-1;j++) {
    			
    			if(visited[i][j] == true) continue;
    			if(visited[i-1][j] == true) continue;
    			if(visited[i][j-1] == true) continue;
    			if(visited[i+1][j] == true) continue;
    			if(visited[i][j+1] == true) continue;
    			
    			visited[i][j] = true;
    			visited[i-1][j] = true;
    			visited[i][j-1] = true;
    			visited[i+1][j] = true;
    			visited[i][j+1] = true;
    			int sum = map[i][j] + map[i-1][j] + map[i][j-1] + map[i+1][j] + map[i][j+1];
    			
    			simulate(level + 1, total + sum);
    			visited[i][j] = false;
    			visited[i-1][j] = false;
    			visited[i][j-1] = false;
    			visited[i+1][j] = false;
    			visited[i][j+1] = false;
    			
    		}
    	}
 
    }
   
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 2615 오목 - 완전탐색 (DFS) JAVA  (0) 2023.07.16
[백준] 2961 도영이가 만든 맛있는 음식 - 완전탐색 (DFS) JAVA  (0) 2023.07.15
[백준] 16508 전공책 - 완전탐색 + 문자열(알파벳) JAVA  (0) 2023.07.14
[백준] 16937 두 스티커 - 완전탐색 + 아이디어 JAVA  (0) 2023.07.14
[백준] 17626 Four Squares - 동적계획법(DP, Dynamic Programming) JAVA  (0) 2023.07.13

+ Recent posts

티스토리툴바