[BaekJoon] 14620 꽃길 (Java)

🔗 문제 링크

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

📝 문제풀이 방법

문제를 풀이할때 처음에는 각각 위치의 cost를 구하고 cost가 작은 위치부터 겹치지 않는 선에서 합을 구하는 식으로 풀이를 하였다. 하지만 이러한 풀이법은 경우에 따라 가장 cost가 적은 위치를 포함하지 않는 최솟값이 나올 수 있기에 잘못된 풀이법이었다.

두번째 풀이법은 3개의 꽃의 위치에 대하여 모든 경우의 수를 탐색하는 방법을 사용하여 풀이를 하였다. 각각 탐색을 하며 꽃이 위치할 수 없는 위치이거나 꽃의 위치가 겹치는 경우는 높은 수를 return하며 정상적인 경우에는 해당 cost를 return후 최솟값을 찾는 식으로 코딩을 하였더니 문제를 해결할 수 있었다.

🔥🔥 새로 알아간 것 🔥🔥
2차원 배열의 경우는 2중 loop가 아닌 아래와 같이 N*N의 탐색 하나만으로도 전체 탐색을 할 수 있다!!

for (int i=0; i<(N*N); i++) {
    x = i/N;
    y= i%N;
}

👨🏻‍💻 작성한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	
	static int[][]matrix;
	static int N;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		matrix = new int[N][N];
		int answer = Integer.MAX_VALUE;
		
		for (int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 3개의 꽃 탐색
		for (int i=0; i<(N*N); i++) {
			for (int j=0; j<(N*N); j++) {
				for (int k=0; k<(N*N); k++) {
					ArrayList<Integer> list = new ArrayList<>();
					list.add(i);
					list.add(j);
					list.add(k);
					answer = Math.min(answer, findCost(list));
				}	
			}
		}
		
		System.out.println(answer);
	}
	static int findCost(ArrayList<Integer> list) {
		int[] dx = {0, -1, 1, 0, 0};
		int[] dy = {0, 0, 0, -1, 1};	
		boolean[][] check = new boolean[N][N];
		
		int result = 0;
		for (int i: list) {
			int x = i / N;
			int y = i % N;
			
			// 가장 자리에 위치하면 탈락
			if (x==0 || x==(N-1) || y==0 || y==(N-1)) {
				return 10000;
			}
			
			for (int j=0; j<5; j++) {
				if (!check[x+dx[j]][y+dy[j]]) {
					check[x+dx[j]][y+dy[j]] = true;
					result += matrix[x+dx[j]][y+dy[j]];
				}
				else return 10000;				
			}
		}
		return result;
	}
}