[백준(Baekjoon)][자바(java)] [삼성 SW 역량 테스트 기출 문제] 14891 : 톱니바퀴

 

www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

문제 풀이

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		final int nw = 4, ns = 8, qs = ns/4;  // num of saw-toothed wheel/saw-tooth, a quarter of ns
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		String t;  int i, j;  // tmp
		boolean p[][] = new boolean[nw][ns];  // saw-toothed wheel pole
		for( i = 0; i < nw; ++i ) {
			t = br.readLine();
			for( j = 0; j < ns; ++j )
				p[i][j] = t.charAt(j)-'0' == 1 ? true : false;
		}
		int k = Integer.parseInt( br.readLine() );
		int r[][] = new int[k][2];  // rotation info
		StringTokenizer st;
		for( i = 0; i < k; ++i ) {
			st = new StringTokenizer( br.readLine() );
			r[i][0] = Integer.parseInt( st.nextToken() ) - 1;
			r[i][1] = Integer.parseInt( st.nextToken() );
		}
		br.close();
	
		int n[] = new int[nw], nr, ec, wc, en, wn, d, c, ic, ir, il;  
		// north index, rotated north index, current/next east/west index, 
		// direction/wheel to rotate, current/next index 
		boolean a[];
		Queue<Integer> q;
		for( i = 0; i < k; ++i ) {
			c = r[i][0];
			a = new boolean[nw];
			a[c] = true;
			q = new LinkedList<>();
			q.add( c );
			while( !q.isEmpty() ) {
				ic = q.remove();
				ir = ic+1;
				il = ic-1;
				if( ir < nw ) {  // right wheel
					ec = n[ic] + qs;  if( ec >= ns )  ec -= ns;
					wn = n[ir] - qs;  if( wn < 0 )  wn += ns;
					if( p[ic][ec] != p[ir][wn] && !a[ir] ) {
						a[ic] = a[ir] = true;
						q.add( ir );
					}
				}
				if( il >= 0 ) {  // left wheel
					wc = n[ic] - qs;  if( wc < 0 )  wc += ns;
					en = n[il] + qs;  if( en >= ns )  en -= ns;
					if( p[ic][wc] != p[il][en] && !a[il] ) {
						a[ic] = a[il] = true;
						q.add( il );
					}
				}
			}
			d = r[i][1];
			d *= c % 2 == 0 ? 1 : -1;
			for( j = 0; j < nw; ++j ) {
				if( a[j] ) {
					nr = n[j];
					nr -= d;
					if( nr >= ns )  nr -= ns;
					if( nr < 0 )  nr += ns;
					n[j] = nr;
				}
				d *= -1;
			}
		}
		
		int s = 0, m = 1;
		for( i = 0; i < nw; ++i ) {
			s += p[i][n[i]] ? m : 0;
			m *= 2;
		}
		
		System.out.println( s );
	}
}

 

*  변수
-  boolean p[4][8]  :  ( each pole of saw-toothed wheel )  톱니바퀴별 각 톱니의 극성
-  int r[k][2]  :  ( rotation info )  회전할 톱니바퀴, 방향 정보
-  boolean a[4]  :  ( array )  k 횟수 동안 각각의 경우 어떤 톱니바퀴를 회전할지 체크
-  int n[4]  :  ( north index )  각 톱니바퀴의 12시( 북쪽 ) 방향 톱니 인덱스
-  int nr  :  ( rotated north index )  회전 후의 〃
-  int ec, wc  :  ( current east/west index )  현재 톱니바퀴의 3시( 동쪽 ) / 9시( 서쪽 ) 방향 톱니 인덱스
-  int en, wn  :  ( next east/west index )  그 옆( 현재와 맞닿는 ) 톱니바퀴의 〃
-  int d  :  ( direction to rotate )  회전 할 방향
-  int w  :  ( saw-toothed wheel to rotate )  회전 할 톱니바퀴 인덱스
-  int ic, il, ir  :  ( current/left/right index )  현재/양옆 〃

*  톱니바퀴 4개의 각각 인덱스는 0, 1, 2, 3 ( 1씩 빼서 취급 )

*  각각의 극성 값을 담을 배열( boolean p[4][8] ) 생성
  -  N극 : 0 => false
  -  S극 : 1 => true

예제 1

*  회전 정보( 톱니바퀴 인덱스( 1씩 빼서 취급 ), 방향 )를 담을 배열( int r[k][2] ) 생성
  -  시계 방향 : 1
  -  반시계 방향 : -1

예제 1

*  톱니바퀴 별 12시 방향 인덱스 배열( int n[4] ) 생성

예제 1  ( 공통 )

*  한 톱니바퀴 당 12시 방향(북쪽)( n : north ) 인덱스, 동쪽( e : east ) 인덱스, 서쪽( w : west ) 인덱스 고려
  -  n  :  n[i]  ( initial : 0 )
  -  e  :  n + 2 ( if e >= 8 then e -= 8 )  ( initial : 2 )
  -  w  :  n - 2 ( if w < 0 then w += 8 )  ( initial : 6 )

*  회전 횟수( k )만큼 루프 돌리며 각 경우마다
  -  회전 할( 맞닿는 톱니바퀴의 극성이 다른 ) 톱니바퀴들을 구하기 위해 배열( boolean a[4] ) 생성
  -  BFS 하며 회전할 톱니바퀴( w : saw-toothed wheel to rotate )로부터 맞닿는 톱니바퀴들의 극성을 비교
   ( 다르면 같이 회전, 방향은 반대 )

  -  배열 a를 탐색하며 회전 할 톱니바퀴들( a[i] == true )을 방향( d : direction to rotate )에 따라 회전
   ( i 번째 north 인덱스 값 변경 => n[i] -= d )
   ( 단, 인접한 톱니바퀴는 서로 반대로 회전해야 하므로 루프 돌며 -1 씩 곱함. c가 짝수면 0번째 회전 방향은 d와 같음 )

예제 1

*  점수 계산
  -  i 번째 톱니바퀴의 12시 방향 톱니( n[i] )의 극( p[i][n[i]] )이 N극( false )이면 0점, S극( true )이면 1점( 2배씩 늘어남 )

*  점수 합 출력