이차원 배열의 원소 인덱스를 뽑는 방법

브루트포스 문제를 풀 때 순열, 조합 등으로 원소 인덱스를 뽑는 과정이 필요하다. 그러면 인덱스가 이차원(x,y)일 경우 어떻게 선택할 수 있을까?

 

아래의 방법으로 쉽게 선택할 수 있다.

 

1. 4X3의 배열일경우 (0,0)은 0으로 (3,4)는 11로 표현할 수 있다. 즉 이차원 인덱스(x,y)를 하나의 정수로 표현할 수 있다. 이 정수로부터 컬럼 크기로 나눈 값이 row, 컬럼 크기로 나머지 연산을 한 값이 col이 된다.

1941번: 소문난 칠공주

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

public class Main {
    /***
     * 1. 서로 다른 25개에서 7개를 뽑는 조합의 수 = 25C7 (이차원 배열에서 7개를 뽑는 방법?)
     * 2. 뽑은 7개에서 S가 4개 이상인지 체크
     * 3. 뽑은 7개가 서로 연결 되어 있는지 체크
     */
    static int[][] pos = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static final int COL_COUNT = 5;
    static char[][] matrix = new char[5][5];

    /***
     * 뽑은 이차원 배열의 원소의 인덱스가 저장되는 리스트 = selectedList
     * 이차원 배열의 원소 인덱스 (row, col)을 하나의 수(rowAndCol)로 표시할 수 있음, rowAndCol = row * col_count + col
     * row = rowAndCol / col_count
     * col = rowAndCol % col_count
     *
     * 예를 들어 4x3 배열에서 (0,0)은 0, (1,2)은 5, (3,2)은 11로 표시 가능
     * 0을 보고 인덱스 (0,0)임을, 5를 보고 인덱스 (1,2)임을 알 수 있음
     */
    static List<Integer> selectedList = new ArrayList<>();
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 5; i++) {
            String str = br.readLine();
            for (int j = 0; j < 5; j++) {
                matrix[i][j] = str.charAt(j);
            }
        }

        combination(0);
        System.out.println(answer);
    }

    static void combination(int rowAndCol) {
        if (selectedList.size() >= 7) {
            if (IsSevenPrincess() && IsConnection()) answer += 1;
            return;
        }

        for (int i = rowAndCol; i < 5 * 5; i++) {
            selectedList.add(i);
            combination(i + 1);
            selectedList.remove(selectedList.size()-1);
        }
    }

    static boolean IsSevenPrincess() {
        int sCount = 0;
        for (int rowAndCol : selectedList) {
            int row = rowAndCol / COL_COUNT;
            int col = rowAndCol % COL_COUNT;
            if (matrix[row][col] == 'S') sCount++;
        }

        if (sCount >= 4) return true;
        return false;
    }

    static boolean IsConnection() {
        int connectCount = 0;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] discovered = new boolean[7];

        connectCount += 1;
        discovered[0] = true;
        queue.add(selectedList.get(0));

        while (!queue.isEmpty()) {
            int rowAndCol = queue.remove();
            int curRow = rowAndCol / COL_COUNT;
            int curCol = rowAndCol % COL_COUNT;

            for (int i = 0; i < 7; i++) {
                if (discovered[i]) continue;
                int targetRowAndCol = selectedList.get(i);
                int targetRow = targetRowAndCol / COL_COUNT;
                int targetCol = targetRowAndCol % COL_COUNT;

                for (int j = 0; j < 4; j++) {
                    int newRow = curRow + pos[j][0];
                    int newCol = curCol + pos[j][1];
                    if (!isRange(newRow, newCol)) continue;
                    if (newRow != targetRow || newCol != targetCol) continue;

                    connectCount += 1;
                    discovered[i] = true;
                    queue.add(selectedList.get(i));
                }
            }
        }

        if (connectCount == 7) return true;
        return false;
    }
    
   static boolean isRange(int row, int col) {
	   return (row >= 0 && row < 5 && col >= 0 && col < 5);
   }
}

 

2. 이차원 인덱스(x,y)를 하나의 클래스로 매핑한다.

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

14620번: 꽃길

/***
 * [문제]
 * 꽃은 중앙과 중앙을 기준을 상,하,좌,우로 핌
 * 꽃은 겹치거나 화단 밖을 나가면 안됨
 * 씨앗을 심어 꽃 3개를 피게하는 최소 대여 비용을 구하는 문제
 * 화단의 한변의 길이(N, 최대 크기 10)
 * 꽃밭(NxN)
 * 화단 가장 바깥은 꽃을 심을 수 없음
 * (N-1)x(N-1)개의 칸에서 씨앗을 심을 3개의 칸을 뽑는 조합의 수 = 81C3
 * 
 * [변수 선언]
 * int[][] score (대여 비용, 시작 인덱스 0,0)
 * 이차원 인덱스를 쉽게 다루는 방법 => Point 객체 또는 rowAndCol(int 변수)
 * Point[] point (x,y를 매핑한 point 객체의 배열)
 * 
 * [해결 과정]
 * 1. (N-1) x (N-1)개의 칸에서 씨앗을 심을 3개를 뽑는 모든 조합을 구한다. (반복문)
 * 2. 각 조합에 대해 대여 비용을 계산한다. 이때 꽃이 겹치는 경우는 계산하지 않는다. 
 * 3. 계산된 대여 비용을 answer와 비교해 최소 대여 비용을 answer에 저장한다.
 */

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

public class Main {
    static int[] xPos = {-1, 1, 0, 0};
    static int[] yPos = {0, 0, -1, 1};
    
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int N = Integer.parseInt(br.readLine());
	    int[][] score = new int[N][N];
	    Point[] point = new Point[(N-2)*(N-2)];
	    int pointIdx = 0;
	    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++) {
	    		score[i][j] = Integer.parseInt(st.nextToken());
	    		if(i==0 || i == (N-1) || j == 0 || j == (N-1)) continue;
	    		point[pointIdx++] = new Point(i, j);
	    	}
	    }
	    
	    //조합
	    for(int i=0; i<point.length; i++) {
	    	for(int j=i+1; j<point.length; j++) {
	    		for(int z=j+1; z<point.length; z++) {
	    			//하나의 조합 완성	    			
	    			if(!isVaild(point[i], point[j], point[z])) continue;
	    			int resultScore = calScore(point[i], point[j], point[z], score);
	    			answer = Math.min(answer, resultScore);
	    		}
	    	}
	    }
	    System.out.println(answer);
	}
	
	static boolean isVaild(Point point1, Point point2, Point point3) {
		//point1, point2 비교
		//대각선
		if(Math.abs(point1.x - point2.x) == 1 && Math.abs(point1.y - point2.y) == 1) return false;
		//행이 같은경우 열차이 3이상 나야함
		if(point1.x == point2.x && Math.abs(point1.y - point2.y) < 3) return false;
		//열이 같은경우 행차이 3이상 나야함
		if(point1.y == point2.y && Math.abs(point1.x - point2.x) < 3) return false;
		
		//point1, point3 비교
		if(Math.abs(point1.x - point3.x) == 1 && Math.abs(point1.y - point3.y) == 1) return false;
		if(point1.x == point3.x && Math.abs(point1.y - point3.y) < 3) return false;
		if(point1.y == point3.y && Math.abs(point1.x - point3.x) < 3) return false;
		
		//point2, point3 비교
		if(Math.abs(point2.x - point3.x) == 1 && Math.abs(point2.y - point3.y) == 1) return false;
		if(point2.x == point3.x && Math.abs(point2.y - point3.y) < 3) return false;
		if(point2.y == point3.y && Math.abs(point2.x - point3.x) < 3) return false;
		
		return true;
	}
	
	static int calScore(Point point1, Point point2, Point point3, int[][] score) {
		int sum = 0;
		Point[] point = new Point[3];
		point[0] = point1;
		point[1] = point2;
		point[2] = point3;
		
		for(int i=0; i<3; i++) {
			sum += score[point[i].x][point[i].y];
			sum += score[point[i].x-1][point[i].y];
			sum += score[point[i].x+1][point[i].y];
			sum += score[point[i].x][point[i].y-1];
			sum += score[point[i].x][point[i].y+1];
		}
		return sum;
	}
}

class Point {
	int x;
	int y;
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}