[BOJ] 백준 17822 원판 돌리기

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

출처: https://www.acmicpc.net/problem/17822

 Input 

4 4 3

1 1 2 3

5 2 4 2

3 1 3 5

2 1 3 2

2 0 1

3 1 3

2 0 2

 

 Output 

22

시뮬레이션

각각의 원에 일정한 간격으로 M(=4)개의 숫자들이 배치되어 있습니다.

특정 좌표 (i, j)에서 인접한 좌표는 (i-1, j) / (i+1, j) / (i, j-1) / (i, j+1)에 해당합니다.

 

▶ (2, 0, 1) = 2, 4번 원판을 시계 방향으로 1칸 회전.

인접한 좌표간에 동일한 숫자가 존재하기에 해당 수들을 모두 지웁니다. 

(지워지지 않은 숫자들의 이동은 없습니다.)

→ 각 원판의 숫자들의 합 = 30

 

 

▶ (3, 1, 3) = 3번 원판을 반시계 방향으로 3칸 회전.

인접한 좌표간에 동일한 숫자가 존재하기에 해당 수들을 모두 지웁니다.

→ 각 원판의 숫자들의 합 = 22

 

 

▶ (2, 0, 2) = 2, 4번 원판을 시계 방향으로 2칸 회전

인접한 좌표간에 동일한 숫자가 없으므로, 지워지지 않은 숫자들의 평균을 구합니다.

평균값(= 22/6 = 3.x)보다 큰 수는 -1 / 작은수는 +1 처리

→ 각 원판의 숫자들의 합 = 22

 

구현

① 원판의 적혀있는 숫자를 이차원 배열로 구현

     → int[][] disk

② 회전 정보에 따라 시계/반시계 방향 구현

     - xi의 배수에 해당하는 원판을 모두 독립적으로 회전

        ex) 2의 배수 = 2, 4, 6, 8, 10...

 

③ 인접한 좌표간 동일한 숫자 존재 여부 확인

     - 접한 좌표를 판단할 때, 끝자리와 처음자리가 인접하는 것으로 처리.

     - BFS or DFS를 통해 어느 범위까지 동일한지 확인

  

④ 인접한 좌표간 동일한 숫자 존재 여부에 따른 처리

    - 존재하는 경우 삭제되었다는 의미로 『0』으로 대체

    - 존재하지 않는 경우 평균값에 따른 숫자 갱신

       평균의 경우 소숫점 처리 → double형

 

※ 회전만 구현했을 때의 결과

 

※ 회전 + 인접한 좌표간 동일한 숫자 존재 여부에 따른 처리

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {	
	static int N, M, T;
	static int x, d, k;
	static int[][] disk;
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static boolean[][] visited;
	static Queue<Node> queue;
	static List<Node> list;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new   InputStreamReader(System.in));
        StringTokenizer st = null;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        
        disk = new int[N+1][M+1];
        for(int i=1; i<=N; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=1; j<=M; j++) {
        		disk[i][j] = Integer.parseInt(st.nextToken());
        	}
        }
        
        while(T-- > 0) { // 회전 정보 개수
        	st = new StringTokenizer(br.readLine());
        	// 회전 원판 (x의 배수)
        	x = Integer.parseInt(st.nextToken());
        	// 회전 방향(시계(0), 반시계(1))
        	d = Integer.parseInt(st.nextToken());
        	// 회전 크기
        	k = Integer.parseInt(st.nextToken());
        	
        	// x 배수에 해당하는 원판들을 독립적으로 회전
        	for(int order=x; order<=N; order = order+x) {
        		rotate(order);
        	}
        	// 인접한 좌표간 동일한 숫자가 있는지 확인
        	if(!findSameNumber()) {
        		// 인접한 곳에 동일한 숫자가 발견되지 않은 경우
        		// 평균에 따른 처리
        		actionByAvg();
        	}
        }
        // 정답출력
        printAnswer();
    }
     
    private static void actionByAvg() {
		double sum = 0;
		double cnt = 0;
		double avg = 0;
		// 평균값 구하기
		for(int r=1 ; r <= N ; ++r) {
			for(int c=1 ; c <= M ; ++c) {
				if(disk[r][c] > 0) {
					sum += disk[r][c];
					cnt++;
				}
			}
		}
		if(cnt == 0) return;
		avg = sum / cnt;
		
		// 평균값을 기준으로 지워지지 않은 숫자에 대한 처리
		for(int r = 1 ; r <= N ; ++r) {
			for(int c = 1 ; c <= M ; ++c) {
				if(disk[r][c] == 0) continue;
				if(disk[r][c] < avg) disk[r][c] += 1;
				else if(disk[r][c] > avg) disk[r][c] -= 1;
			}
		}
	}

	private static boolean findSameNumber() {
		boolean isSameNum = false;
		visited = new boolean[N+1][M+1];
		queue = new LinkedList<Node>();
		// 인접한 좌표간 동일한 숫자들이 몇개 있는지 확인하는 리스트
		list = new ArrayList<Node>();
		// 모든 영역에 대해 BFS 탐색
		for(int r=1 ; r <= N ; r++) {
			for(int c=1 ; c <= M ; c++) {
				// 이미 방문한 곳이거나 제거된 곳이면 continue
				if(disk[r][c] == 0 || visited[r][c]) continue;
				Node current = new Node(r, c);
				list.add(current);
				queue.offer(current);
				
				// 기준값 전달
				BFS(disk[r][c]);
				// BFS결과 인접한 곳에 동일한 숫자가 2개 이상 있다면
				if(list.size() > 1) {
					isSameNum = true;
					for(Node node : list) {
						// 원판에서 숫자 제거
						disk[node.r][node.c] = 0;
					}
				}
				list.clear();
			}
		}
		return isSameNum;
	}

	private static void BFS(int targetNum) {
		while(!queue.isEmpty()) {
			Node current = queue.poll();
			
			for(int i = 0 ; i < 4 ; ++i) {
				int nR = current.r + dr[i];
				int nC = current.c + dc[i];
				
				// 한 행에서 양쪽 끝은 원판에서 인접한 좌표 
				if(nC > M) nC = 1;
				else if(nC < 1) nC = M;
				
				// 범위를 벗어나거나 방문한 곳이면 continue
				if(nR > N || nR < 1 || visited[nR][nC]) continue;
				
				// 인접한 좌표가 같은 숫자인 경우
				if(disk[nR][nC] == targetNum) {
					visited[nR][nC] = true;
					Node next = new Node(nR, nC);
					queue.offer(next);
					list.add(next);
				}
			}
		}
	}

	private static void rotate(int order) {
    	// 주어진 회전 크기만큼 원판 회전시킵니다.
		for(int cnt=1; cnt<=k; cnt++) {
			// 시계 방향
			if(d == 0) { 
		    	int temp = disk[order][M];
		    	for(int i=M; i>1; i--) {
		    		disk[order][i] = disk[order][i-1];
		    	}
		    	disk[order][1] = temp;
	    	}
			// 반시계 방향
	    	else { 
	    		int temp = disk[order][1];
		    	for(int i=1; i<M; i++) {
		    		disk[order][i] = disk[order][i+1];
		    	}
		    	disk[order][M] = temp;
	    	}
		}
	}

	public static void printAnswer() {
		int sum = 0;
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=N; i++) {
        	for(int j=1; j<=M; j++) {
        		sum += disk[i][j];
        	}
        }
        sb.append(sum);
        System.out.println(sb.toString());
    }
}

class Node{
	int r, c;
	Node(int r, int c){
		this.r = r;
		this.c = c;
	}
}