[코드트리/INTERMEDIATE LOW] 1차원 바람 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• 시뮬레이션, 재귀

1. 바람이 처음 분 r번째 행을 해당 방향으로 shift 한다.

2. 바로 윗 줄과 아랫 줄의 같은 열에서 같은 값이 존재한다면, 그 줄은 현재 바람 방향의 반대 방향으로 shift해준다. (재귀)

 

> 시간 복잡도 : O(NMQ)

 

 

 

💥 유의사항

격자 범위 벗어나지 않도록 신경쓰기,,

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, Q;
    static int[][] map;
    static boolean[] visited;   // 각 행 방문 여부 확인 배열
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
 
        map = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        while(Q --> 0) {
            String[] str = br.readLine().split(" ");
            int r = Integer.parseInt(str[0]);   // 바람에 영향 받는 행 번호
            char d = str[1].charAt(0);          // 바람이 불어오는 방향
 
            visited = new boolean[N + 1];
            wind(r, d);
        }
 
        print();
    }
 
    private static void wind(int r, char d) {
        if(r < 1 || r > N || visited[r])  return;
 
        visited[r] = true;
 
        if(d == 'L') {
            // r번째 행 오른쪽으로 shift하기
            int val = map[r][M];
 
            for(int i = M ; i > 1 ; i--) {
                map[r][i] = map[r][i - 1];
            }
 
            map[r][1] = val;
 
            // 바로 윗 줄과 아랫 줄의 같은 열에 같은 값이 있는지 확인하고 shift할지 결정
            boolean isSame1 = false;
            for(int i = 1 ; i <= M ; i++) {
                if(((r - 1) >= 1) && map[r][i] == map[r - 1][i]) {
                    isSame1 = true;
                    break;
                }
            }
 
            boolean isSame2 = false;
            for(int i = 1 ; i <= M ; i++) {
                if(((r + 1) <= N) && map[r][i] == map[r + 1][i]) {
                    isSame2 = true;
                    break;
                }
            }
 
            if(isSame1) wind(r - 1, 'R');
            if(isSame2) wind(r + 1, 'R');
        }
        else if(d == 'R') {
            // r번째 행 왼쪽으로 shift하기
            int val = map[r][1];
 
            for(int i = 1 ; i < M ; i++) {
                map[r][i] = map[r][i + 1];
            }
 
            map[r][M] = val;
 
            // 바로 윗 줄과 아랫 줄의 같은 열에 같은 값이 있는지 확인하고 shift할지 결정
            boolean isSame1 = false;
            for(int i = 1 ; i <= M ; i++) {
                if(((r - 1) >= 1) && map[r][i] == map[r - 1][i]) {
                    isSame1 = true;
                    break;
                }
            }
 
            boolean isSame2 = false;
            for(int i = 1 ; i <= M ; i++) {
                if(((r + 1) <= N) && map[r][i] == map[r + 1][i]) {
                    isSame2 = true;
                    break;
                }
            }
 
            if(isSame1) wind(r - 1, 'L');
            if(isSame2) wind(r + 1, 'L');    
        }      
    }
 
    // 출력 메소드
    private static void print() {
        StringBuilder sb = new StringBuilder();
        for(int i = 1;  i <= N ; i++) {
            for(int j = 1 ; j <= M ; j++) {
                sb.append(map[i][j] + " ");
            }
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
}

 

 

---

💦 어려웠던 점

- 윗줄과 아랫줄을 일일이 반복문으로 방문할까 하다가 재귀함수를 사용하였다.

- 격자 범위를 벗어나거나, 빠지는 조건이 없는지 신경써야 한다.

 

 

1회독	2회독	3회독	4회독	5회독
V