[SWEA/Java] 프로세서 연결하기 (1767)

프로세서 연결하기 (1767)

1. 문제 분석

문제 개요

• N x N 크기의 프로세서 셀(cell) 맵에서 가능한 최대 코어(core)를 연결하고, 그에 필요한 최소 전선 길이를 구하는 문제이다.

입력 형식

• 첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.
• 각 테스트 케이스의 첫 줄에 셀의 크기 N이 주어진다.
• 다음 N줄에 걸쳐 N x N 셀 정보가 주어진다.

출력 형식

• 각 테스트 케이스에 대해 "#테스트케이스번호 최소 전선 길이" 형식으로 출력한다.

2. 알고리즘 종류

• 이 문제는 백트래킹(Backtracking) 알고리즘을 사용하여 해결한다. 백트래킹을 통해 가능한 모든 코어 연결 경우를 탐색하고 최적의 해를 찾는다.

3. 주요 부분 및 코드 작성 방법

1. 입력 처리 및 초기화

• 입력을 받아 프로세서 셀 맵을 초기화하고, 코어의 위치를 저장한다.

2. 백트래킹을 통한 코어 연결

• 백트래킹을 사용하여 모든 코어를 가능한 방법으로 연결한다.
• 연결된 코어의 개수와 사용된 전선의 길이를 통해 최소 전선 길이를 계산한다.

3. 결과 출력

• 각 테스트 케이스의 결과를 출력 형식에 맞게 출력한다.

아래와 같이 주어진 코드에 대해 세분화된 설명을 추가했습니다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리 및 초기화

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
    StringBuilder sb = new StringBuilder(); // 결과 출력을 위한 StringBuilder 객체 생성
    StringTokenizer st;
  
    int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수 입력 받기

  • BufferedReader 객체를 통해 입력을 처리한다.
  • StringBuilder 객체를 생성하여 결과 출력을 준비한다.
  • 테스트 케이스의 수 T를 입력받는다.

• 테스트 케이스 반복 및 셀 정보 초기화

    for (int tc = 1; tc <= T; tc++) { // 각 테스트 케이스에 대해 반복
        N = Integer.parseInt(br.readLine()); // 셀 크기 N 입력 받기
        cell = new int[N][N]; // N x N 셀 배열 초기화
        coreList = new ArrayList<>(); // 코어 위치를 저장할 리스트 초기화

  • 각 테스트 케이스마다 셀의 크기 N을 입력받고, 셀 배열과 코어 위치 리스트를 초기화한다.

• 셀 정보 입력 및 코어 위치 저장

    for (int r = 0; r < N; r++) { // 각 셀 정보를 입력 받기
        st = new StringTokenizer(br.readLine());
        for (int c = 0; c < N; c++) {
            cell[r][c] = Integer.parseInt(st.nextToken()); // 셀의 상태 입력 받기
            if (r < 1 || c < 1 || r >= N - 1 || c >= N - 1) continue; // 가장자리 제외
            if (cell[r][c] == 1) coreList.add(new Point(c, r)); // 코어 위치 추가
        }
    }

  • StringTokenizer를 사용하여 각 행(row)에 대한 셀 정보를 입력받는다.
  • 셀의 상태가 1인 경우, 해당 코어가 가장자리에 위치하지 않았다면 코어 리스트에 추가한다.

• 초기 상태 설정 및 백트래킹 시작

    minWire = Integer.MAX_VALUE; // 최소 전선 길이 초기화
    maxCore = Integer.MIN_VALUE; // 최대 연결 코어 수 초기화
  
    connect(0, 0, 0); // 백트래킹 함수 호출
    sb.append("#" + tc + " " + minWire + "\n"); // 결과 저장
    }
    System.out.println(sb); // 결과 출력

  • minWire와 maxCore를 초기화한다.
  • 백트래킹을 시작하여 가능한 모든 코어 연결 경우를 탐색한다.
  • 각 테스트 케이스의 결과를 StringBuilder에 저장하고 마지막에 출력한다.

(2) 코어 연결 백트래킹 함수 (connect)

• 기저 조건 검사

    if (idx == coreList.size()) { // 모든 코어를 처리한 경우
        if (maxCore < coreCnt) { // 현재 코어 개수가 최대 코어 개수보다 큰 경우
            maxCore = coreCnt; // 최대 코어 개수 업데이트
            minWire = wireCnt; // 최소 전선 길이 업데이트
        } else if (maxCore == coreCnt) {
            minWire = Math.min(wireCnt, minWire); // 코어 개수가 같다면 최소 전선 길이 업데이트
        }
        return; // 함수 종료
    }

  • 모든 코어를 처리한 경우, 현재 코어 개수가 최대 코어 개수보다 크거나 같은지 확인하고, 최소 전선 길이를 업데이트한다.
  • 기저 조건에 해당하면 함수가 종료된다.

• 코어 좌표 추출

    int c = coreList.get(idx).x; // 현재 코어의 열 좌표
    int r = coreList.get(idx).y; // 현재 코어의 행 좌표

  • 현재 처리할 코어의 좌표(열, 행)를 추출한다.

• 네 방향으로 전선 연결

    for (int dir = 0; dir < 4; dir++) { // 네 방향으로 전선 연결 시도
        int count = 0; // 전선 길이 초기화
        int nc = c; // 열 좌표 초기화
        int nr = r; // 행 좌표 초기화
  
        while (true) { // 전선 연결 가능 여부 확인
            nc += dc[dir]; // 방향에 따른 열 좌표 이동
            nr += dr[dir]; // 방향에 따른 행 좌표 이동
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) break; // 경계를 벗어나면 종료
  
            if (cell[nr][nc] == 1) { // 다른 코어나 전선과 겹치면 종료
                count = 0; // 전선 길이 초기화
                break;
            }
            count++; // 전선 길이 증가
        }

  • 네 가지 방향(상, 하, 좌, 우)에 대해 전선을 연결할 수 있는지 확인한다.
  • 전선이 다른 코어나 전선에 겹치는 경우, 해당 방향으로의 연결을 포기한다.

• 전선 연결 및 백트래킹 호출

    int fill_c = c; // 연결된 전선의 열 좌표
    int fill_r = r; // 연결된 전선의 행 좌표
  
    for (int i = 0; i < count; i++) { // 전선을 맵에 표시
        fill_c += dc[dir];
        fill_r += dr[dir];
        cell[fill_r][fill_c] = 1; // 전선 표시
    }
  
    if (count == 0) // 전선을 연결하지 않은 경우
        connect(idx + 1, coreCnt, wireCnt); // 다음 코어 처리
    else {
        connect(idx + 1, coreCnt + 1, wireCnt + count); // 전선을 연결한 경우
  
        fill_c = c; // 전선을 다시 제거
        fill_r = r;
        for (int i = 0; i < count; i++) { 
            fill_c += dc[dir];
            fill_r += dr[dir];
            cell[fill_r][fill_c] = 0; // 전선 제거
        }
    }

  • 전선을 연결할 수 있는 경우, 전선을 셀 맵에 표시하고 다음 코어를 백트래킹 방식으로 처리한다.
  • 백트래킹 이후에는 전선을 제거하여 상태를 원래대로 되돌린다.

5. 전체 코드

package SWEA.Day0830.SWEA프로세서_연결하기;

import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class SWEA1767 {
    static int N, minWire, maxCore; // 셀의 크기, 최소 전선 길이, 최대 연결된 코어 수
    static int[][] cell; // 셀의 상태를 저장할 2차원 배열
    static List<Point> coreList; // 코어의 위치를 저장할 리스트
    static int[] dr = {-1, 1, 0, 0}; // 행 방향 이동 배열
    static int[] dc = {0, 0 ,-1, 1}; // 열 방향 이동 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
        StringBuilder sb = new StringBuilder(); // 결과 출력을 위한 StringBuilder 객체 생성
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수 입력 받기

        for (int tc = 1; tc <= T; tc++) { // 각 테스트 케이스에 대해 반복
            N = Integer.parseInt(br.readLine()); // 셀 크기 N 입력 받기
            cell = new int[N][N]; // N x N 셀 배열 초기화
            coreList = new ArrayList<>(); // 코어 위치를 저장할 리스트 초기화

            for (int r = 0; r < N; r++) { // 각 셀 정보를 입력 받기
                st = new StringTokenizer(br.readLine());
                for (int c = 0; c < N; c++) {
                    cell[r][c] = Integer.parseInt(st.nextToken()); // 셀의 상태 입력 받기
                    if (r < 1 || c < 1 || r >= N - 1 || c >= N - 1) continue; // 가장자리 제외
                    if (cell[r][c] == 1) coreList.add(new Point(c, r)); // 코어 위치 추가
                }
            }
            minWire = Integer.MAX_VALUE; // 최소 전선 길이 초기화
            maxCore = Integer.MIN_VALUE; // 최대 연결 코어 수 초기화

            connect

(0, 0, 0); // 백트래킹 함수 호출
            sb.append("#" + tc + " " + minWire + "\n"); // 결과 저장
        }
        System.out.println(sb); // 결과 출력
    }

    public static void connect(int idx, int coreCnt, int wireCnt) { // idx번째 코어를 처리하는 함수
        if(idx == coreList.size()) { // 모든 코어를 처리한 경우
            if(maxCore < coreCnt) { // 현재 코어 개수가 최대 코어 개수보다 큰 경우
                maxCore = coreCnt; // 최대 코어 개수 업데이트
                minWire = wireCnt; // 최소 전선 길이 업데이트
            } else if(maxCore == coreCnt) minWire = Math.min(wireCnt, minWire); // 코어 개수가 같다면 최소 전선 길이 업데이트
            return; // 함수 종료
        }
        int c = coreList.get(idx).x; // 현재 코어의 열 좌표
        int r = coreList.get(idx).y; // 현재 코어의 행 좌표

        for(int dir = 0; dir < 4; dir++) { // 네 방향으로 전선 연결 시도
            int count = 0; // 전선 길이 초기화
            int nc = c; // 열 좌표
            int nr = r; // 행 좌표

            while(true) { // 전선 연결 가능 여부 확인
                nc += dc[dir]; // 방향에 따른 열 좌표 이동
                nr += dr[dir]; // 방향에 따른 행 좌표 이동
                if(nr < 0 || nr >= N || nc < 0 || nc >= N)  break; // 경계를 벗어나면 종료

                if (cell[nr][nc] == 1) { // 다른 코어나 전선과 겹치면 종료
                    count = 0; // 전선 길이 초기화
                    break;
                }
                count++; // 전선 길이 증가
            }
            int fill_c = c; // 연결된 전선의 열 좌표
            int fill_r = r; // 연결된 전선의 행 좌표

            for(int i=0; i<count; i++) { // 전선을 맵에 표시
                fill_c += dc[dir];
                fill_r += dr[dir];
                cell[fill_r][fill_c] = 1; // 전선 표시
            }

            if(count==0) // 전선을 연결하지 않은 경우
                connect(idx+1, coreCnt, wireCnt); // 다음 코어 처리
            else {
                connect(idx+1, coreCnt+1, wireCnt+count); // 전선을 연결한 경우

                fill_c = c; // 전선을 다시 제거
                fill_r = r;
                for(int i=0; i<count; i++) { 
                    fill_c += dc[dir];
                    fill_r += dr[dir];
                    cell[fill_r][fill_c] = 0; // 전선 제거
                }
            }
        }
    }
}