정범의 프로그래밍 블로그 입니다.

8 분 소요

1. 문제 접근 방법 및 아이디어

이 문제의 핵심 아이디어는 영향력이 전파되는 방향과 실제 회전 처리를 분리하는 것 입니다.

  1. 방향성 확인
    • 특정 자석이 회전할 때, 왼쪽과 오른쪽으로 가며 인접한 자석들과의 접점(맞닿은 극)이 서로 다른지 확인하여 회전 여부를 결정합니다.
  2. 독립적 결정
    • 자석 A가 돌아서 B가 도는 것이 아니라, A가 돌기 전의 상태를 기준으로 B의 회전 여부가 결정됩니다.
    • 따라서 모든 자석의 회전 방향을 먼저 결정한 뒤 한꺼번에 돌려야 합니다.
  3. 회전 처리
    • 8개의 날을 가진 자석을 시계/반시계 방향으로 회전시키는 배열 인덱스 조작이 필요합니다.
  4. 점수 계산
    • 모든 회전 명령이 끝난 뒤 1번 날의 값을 합산합니다.

2. 필요한 개념 및 알고리즘

  1. 시뮬레이션
    • 문제에 제시된 조건을 그대로 코드로 구현해야 합니다.
    • 최적의 해를 찾는 것이 아니라, 정해진 명령을 수행한 후의 최종 상태를 묻고 있기 때문입니다.
  2. 재귀
    • 현재 자석에서 좌/우로 뻗어나가며 반응을 확인하기 위해 필요합니다.
    • “하나의 자석이 회전할 때 인접한 자석이 극이 다르면.. 연쇄적으로 회전한다”라는 문구 자체가 재귀적 정의를 포함하고 있습니다.
  3. 배열 및 인덱스 조작
    • 자석의 8개 날을 관리하고 회전시키는데 필수적입니다.

3. 어려웠던 포인트

  1. 회전 시점의 딜레마
    • 이 문제에서는 이웃을 확인하기 전의 내 상태 기준으로 이웃의 회전 여부를 결정해햐 하므로, 반드시 이웃 확인 로직이 배열 회전 로직보다 먼저 나와야 합니다.
  2. 무한 재귀
    • 현재 자석이 어느 방향에서 왔는지(오른쪽/왼쪽)를 체크하지 않으면 이미 확인한 자석을 다시 확인하여 무한 루프에 빠집니다.

4. 코드 풀이

4.1 자석 회전 메인 로직

// 자석의 회전 정보 입력
for (int i = 0; i < K; i++) {
    // 자석의 번호와 방향 입력
    st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
	int d = Integer.parseInt(st.nextToken());
 
	// 1 ~ 4번 자석 방향 체크 초기화
    diretion = new int[5];
                 
    // 방향 체크
    process(n,d);
 
    // 회전 진행
    for (int j = 1; j <= 4; j++) {
        if(diretion[j] != 0) 
            rotate(j,diretion[j]);
    }
                 
} // 입력 종료
  • 준비: 회전 방향 배열을 초기화
  • 탐색: 연쇄 회전 여부 판별
  • 실행: 결저오딘 방향으로 실제 회전

4.2 자석 연쇄 회전 결정 함수

4.2.1 현재 자석의 방향 설정

// 회전 방향 저장
diretion[id] = dir;
  • 현재 자석이 어느 방향으로 회전할지 저장합니다.
  • 중복 탐색을 방지하는 방문체크 역할도 겸합니다.

4.2.2 왼쪽 탐색 코드

if (id > 1 && diretion[id - 1] == 0) {
    if (magne[id][6] != magne[id - 1][2]) {
        process(id - 1, -dir);
    }
}
  • if (id > 1 && direction[id - 1] == 0)은 탐색 가능 조건을 체크합니다.
    • id>1은 현재 자석이 1번이면 그 왼쪽에는 더 이상 자석이 없다는 의미입니다.
    • direction[id -1]은 회전 방향이 결정되지 않았는지 확인합니다.
    • 만약 이미 방향이 결정된 자석을 다시 체크하면 무한 루프에 빠지기 때문입니다.
  • if (magne[id][6] != magne[id - 1][2])은 자성 비교를 합니다.
    • 문제에서 나온 입접한 인덱스가 서로 다르면 왼쪽 자석을 반대 방향 회전시킵니다.

4.2.3 오른쪽 탐색 코드

 if (id < 4 && diretion[id + 1] == 0) {
    if (magne[id][2] != magne[id + 1][6]) {
    	process(id + 1, -dir);
    }
}
  • if (id < 4 && direction[id + 1] == 0)은 탐색 가능 조건을 체크합니다.
    • id<4은 현재 자석이 4번이면 그 오른쪽에는 더 이상 자석이 없다는 의미입니다.
    • direction[id +1]은 회전 방향이 결정되지 않았는지 확인합니다.
    • 만약 이미 방향이 결정된 자석을 다시 체크하면 무한 루프에 빠지기 때문입니다.
  • if (magne[id][2] != magne[id + 1][6])은 자성 비교를 합니다.
    • 문제에서 나온 입접한 인덱스가 서로 다르면 오른쪽 자석을 반대 방향 회전시킵니다.

4.2.4 process 함수 전체 코드

// 이웃한 자석이 회전 가능한지 체크하는 함수
static void process(int id, int dir) {
 
    // 회전 방향 저장
    diretion[id] = dir;
 
    // 왼쪽 탐색
    // 왼쪽에 회전할 자석이 존재하고, 회전 체크가 안될 경우 진행
    // id가 1이면 더 이상 탐색할 자석이 없기 때문
    // 회전 체크하는 이유는 재귀할 때 이미 체크한 곳을 다시 확인하는 것을 방지
    if (id > 1 && diretion[id - 1] == 0) {
 
        // 자신의 6번과 오른쪽의 2번이 붙어 있는 자석이다.
        // 붙어 있는 자석이 서로 다르면 반대 방향으로 1칸 회전한다.
        if (magne[id][6] != magne[id - 1][2]) {
            process(id - 1, -dir);
        }
 
    }
 
    // 오른쪽 탐색
    // 오른쪽에 회전할 자석이 존재하고, 회전 체크가 안될 경우 진행
    // id가 4이면 더 이상 탐색할 자석이 없기 때문
    // 회전 체크하는 이유는 재귀할 때 이미 체크한 곳을 다시 확인하는 것을 방지
    if (id < 4 && diretion[id + 1] == 0) {
 
        // 자신의 2번과 왼쪽 6번이 붙어 있는 자석이다.
        // 붙어 있는 자석이 서로 다르면 반대 방향으로 1칸 회전한다.
        if (magne[id][2] != magne[id + 1][6]) {
            process(id + 1, -dir);
        }
    }
 
} // 체크 함수 종료

4.3 roate 함수

4.3.1 시계 방향 회전

// 시계 방향 회전
// 오른쪽 시프트 연산
// 맨 뒤의 원소 추출
int temp = magne[id][7];
             
// 원소 오른쪽으로 이동
for (int i = 7; i > 0; i--) {
    magne[id][i] = magne[id][i-1];
}
             
// 첫번째 원소 갱신
magne[id][0] = temp;
  • 시계 방향 회전은 오른쪽 시프트 연산이라고 생각하면 됩니다.
  • 오른쪽 시프트 연산할 때 배열의 마지막 원소는 사라질 수 있기 때문에 미리 임시로 추출합니다.
  • 배열의 뒤에서부터 순회하며 앞의 값을 뒤로 옯깁니다. (i번째에 i-1의 값을 대입)
  • 비어있는 맨 앞자리(magne[id][0])에 임시로 추출한 값을 넣습니다.

4.3.2 반시계 방향 회전

// 반시계 회전
 // 왼쪽 시프트 연산
// 맨 앞에 원소 추출
int temp = magne[id][0];
             
// 원소 왼쪽으로 이동
for (int i = 0; i < 7; i++) {
    magne[id][i] = magne[id][i+1];
}
             
// 마지막 원소 갱신
magne[id][7] = temp;
  • 반시계 방향 회전은 왼쪽 시프트 연산이라고 생각하면 됩니다.
  • 왼쪽 시프트 연산할 때 배열의 첫번째 원소는 사라질 수 있기 때문에 미리 임시로 추출합니다.
  • 배열의 앞에서부터 순회하며 앞의 값을 뒤로 옯깁니다. (i번째에 i+1의 값을 대입)
  • 비어있는 맨 뒷자리(magne[id][7])에 임시로 추출한 값을 넣습니다.

4.3.3 rotate 함수 전체 코드

// 회전하는 함수
static void rotate(int id, int dir) {
    // 시계 방향 회전
    // 오른쪽 시프트 연산
    if(dir==1) {
    	// 맨 뒤의 원소 추출
        int temp = magne[id][7];
             
        // 원소 오른쪽으로 이동
        for (int i = 7; i > 0; i--) {
            magne[id][i] = magne[id][i-1];
        }
             
        // 첫번째 원소 갱신
        magne[id][0] = temp;
             
    }
    // 반시계 회전
    // 왼쪽 시프트 연산
    else {
             
        // 맨 앞에 원소 추출
        int temp = magne[id][0];
             
        // 원소 왼쪽으로 이동
        for (int i = 0; i < 7; i++) {
            magne[id][i] = magne[id][i+1];
        }
             
        // 마지막 원소 갱신
        magne[id][7] = temp;
    }
         
 
} // 회전 함수 종료

4.4

// 점수를 계산하는 함수
static int getScore() {
    int score = 0;
 
    if (magne[1][0] != 0)
        score += 1;
    if (magne[2][0] != 0)
        score += 2;
    if (magne[3][0] != 0)
        score += 4;
    if (magne[4][0] != 0)
        score += 8;
 
    return score;
}
  • 1번 ~ 4번까지 자석의 첫번째 원소가 1이면 각각 1, 2, 4, 8점을 준다.

4.5 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int[][] magne = new int[5][8]; // 자성 정보
    static int diretion[]; // 자석의 방향 모음
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine().trim());
 
        // tc 수행
        for (int tc = 1; tc <= T; tc++) {
 
            // 입력 변수
            StringTokenizer st;
 
            // 자석을 회전시키는 횟수 입력
            int K = Integer.parseInt(br.readLine().trim());
 
            // 자성 정보 입력
            for (int i = 1; i <= 4; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 8; j++) {
                    magne[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
            // 자석의 회전 정보 입력
            for (int i = 0; i < K; i++) {
                // 자석의 번호와 방향 입력
                st = new StringTokenizer(br.readLine());
                int n = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());
 
                // 1 ~ 4번 자석 방향 체크 초기화
                diretion = new int[5];
                 
                // 방향 체크
                process(n,d);
 
                // 회전 진행
                for (int j = 1; j <= 4; j++) {
                    if(diretion[j] != 0) 
                        rotate(j,diretion[j]);
                }
                 
            } // 입력 종료
 
            // 출력 내용 추가
            sb.append("#" + tc + " " + getScore() + "\n");
 
        } // tc 종료
 
        // 출력
        System.out.println(sb);
 
    } // 메인 종료
 
    // 이웃한 자석이 회전 가능한지 체크하는 함수
    static void process(int id, int dir) {
 
        // 회전 방향 저장
        diretion[id] = dir;
 
        // 왼쪽 탐색
        // 왼쪽에 회전할 자석이 존재하고, 회전 체크가 안될 경우 진행
        // id가 1이면 더 이상 탐색할 자석이 없기 때문
        // 회전 체크하는 이유는 재귀할 때 이미 체크한 곳을 다시 확인하는 것을 방지
        if (id > 1 && diretion[id - 1] == 0) {
 
            // 자신의 6번과 오른쪽의 2번이 붙어 있는 자석이다.
            // 붙어 있는 자석이 서로 다르면 반대 방향으로 1칸 회전한다.
            if (magne[id][6] != magne[id - 1][2]) {
                process(id - 1, -dir);
            }
 
        }
 
        // 오른쪽 탐색
        // 오른쪽에 회전할 자석이 존재하고, 회전 체크가 안될 경우 진행
        // id가 4이면 더 이상 탐색할 자석이 없기 때문
        // 회전 체크하는 이유는 재귀할 때 이미 체크한 곳을 다시 확인하는 것을 방지
        if (id < 4 && diretion[id + 1] == 0) {
 
            // 자신의 2번과 왼쪽 6번이 붙어 있는 자석이다.
            // 붙어 있는 자석이 서로 다르면 반대 방향으로 1칸 회전한다.
            if (magne[id][2] != magne[id + 1][6]) {
                process(id + 1, -dir);
            }
        }
 
    } // 체크 함수 종료
 
    // 회전하는 함수
    static void rotate(int id, int dir) {
        // 시계 방향 회전
        // 오른쪽 시프트 연산
        if(dir==1) {
            // 맨 뒤의 원소 추출
            int temp = magne[id][7];
             
            // 원소 오른쪽으로 이동
            for (int i = 7; i > 0; i--) {
                magne[id][i] = magne[id][i-1];
            }
             
            // 첫번째 원소 갱신
            magne[id][0] = temp;
             
        }
        // 반시계 회전
        // 왼쪽 시프트 연산
        else {
             
            // 맨 앞에 원소 추출
            int temp = magne[id][0];
             
            // 원소 왼쪽으로 이동
            for (int i = 0; i < 7; i++) {
                magne[id][i] = magne[id][i+1];
            }
             
            // 마지막 원소 갱신
            magne[id][7] = temp;
        }
         
 
    } // 회전 함수 종료
 
    // 점수를 계산하는 함수
    static int getScore() {
        int score = 0;
 
        if (magne[1][0] != 0)
            score += 1;
        if (magne[2][0] != 0)
            score += 2;
        if (magne[3][0] != 0)
            score += 4;
        if (magne[4][0] != 0)
            score += 8;
 
        return score;
 
    }
 
}

카테고리:

업데이트:

참고

상호의 배틀필드

6 분 소요

1. 문제 접근 방법 및 아이디어 초기 상태 파악 2차원 배열을 입력받으며 전차의 초기 위치(r,c)와 방향(d)을 저장합니다. 명령어 해석 문자열로 주어진 명령을 순차적으로 읽으며 Move와 shoot을 분기 처리합니...

현주가 좋아하는 제곱근 놀이

2 분 소요

1. 문제 접근 방법 및 아이디어 이 문제의 핵심은 숫자 N을 2로 만드는 가장 빠른 방법을 찾는 것입니다. 그리디 N이 완전제곱수라면 무조건 루트를 씌우는 것이 이득입니다. 숫자가 비약적으로 작아지기 때문입니다. 점프 ...

규영이와 인영이의 카드게임

4 분 소요

1. 문제 접근 방법 및 아이디어 이 문제는 규영이의 카드 순서는 고정되어 있고, 인영이가 가진 9장의 카드를 어떤 순서로 내느냐에 따라 승패가 결정되는 문제입니다. 데이터 분리 전체 1 ~ 18 카드 중 규영이가 가진 9장을 제외한 나머지 9장을 인영이의...

햄스터

4 분 소요

1. 문제 접근 방법 및 아이디어 이 문제는 모든 가능한 햄스터의 배치 중 조건을 만족하면서 합이 최대인 경우를 찾는 것이 핵심입니다. 배치 생성 각 우리(1 ~ N)에 들어갈 수 있는 햄스터 수는 0마리부터 X까지 입니다. 모든 경우의 ...