[코드트리/INTERMEDIATE LOW] 숫자의 순차적 이동 (JAVA)

📖 문제

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

 

 

 

💡  풀이 방식

• 시뮬레이션

숫자 1부터 N*N까지

 

1. 해당 숫자의 위치를 찾고,

2. 해당 숫자가 있는 칸 주변의 8방향을 탐색해 가장 큰 숫자가 있는 칸의 위치를 찾는다.

3. 2에서 구한 위치와 1에서 구한 위치의 값을 swap한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};   // 8방향
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
 
    static int N, M;
    static int[][] grid;
 
    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());   // 턴 수
 
        grid = new int[N][N];
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        while(M --> 0) {
            for(int k = 1 ; k <= N * N ; k++) {
                int[] pos = findPos(k);             // 1. 해당 숫자 위치 찾기
                int[] nextPos = findNextPos(pos);   // 2. 해당 숫자의 8방향 탐색해서 가장 큰 숫자의 위치 찾기
                swap(pos, nextPos);                 // 3. 인접한 칸 중 가장 큰 숫자를 갖고 있는 칸과 현재 위치의 값 swap하기
            }
        }
 
        print();
    }
 
    // 1) 해당 숫자 위치 찾는 메소드
    private static int[] findPos(int x) {
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(grid[i][j] == x) {
                    return new int[] {i, j};
                }
            }
        }
 
        return new int[] {0, 0};
    }
 
    // 2) 해당 숫자의 8방향 탐색해서 가장 큰 숫자의 위치 찾는 메소드
    private static int[] findNextPos(int[] arr) {
        int x = arr[0];
        int y = arr[1];
 
        int[] pos = new int[2];
        int max = -1;
 
        for(int d = 0 ; d < 8 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if(inRange(nx, ny) && grid[nx][ny] > max) {
                max = grid[nx][ny];
                pos = new int[] {nx, ny};
            }
        }
 
        return pos;
    }
 
    // 3) 인접한 칸 중 가장 큰 숫자를 갖고 있는 칸과 현재 위치의 값 swap하는 메소드
    private static void swap(int[] arr1, int[] arr2) {
        int x = arr1[0];
        int y = arr1[1];
 
        int nx = arr2[0];
        int ny = arr2[1];
 
        int tmp = grid[x][y];
        grid[x][y] = grid[nx][ny];
        grid[nx][ny] = tmp;
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < N);
    }
 
    // 출력 메소드
    private static void print() {
        StringBuilder sb = new StringBuilder();
        for(int[] i : grid) {
            for(int j : i)
                sb.append(j + " ");
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
}

 

 

---

💦 어려웠던 점

 

로직은 다 맞게 썼던 것 같은데 그냥 한 메소드 안에 다 로직을 넣다보니

swap해서 변경된 이후의 값이 반영되지 않은 상태로 1~N*N까지 다음 프로세스를 진행하려고 했던 것 같다.

 

다음에는 무조건 저 정답코드처럼 다 메소드 나눠서 작성해야지,,

틀린 코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};   // 8방향
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
 
    static int N, M;
    static int[][] grid;
 
    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());   // 턴 수
 
        grid = new int[N][N];
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        while(M --> 0) {
            for(int k = 1 ; k <= N * N ; k++) {
                for(int i = 0 ; i < N ; i++) {        // 틀린 부분
                    for(int j = 0 ; j < N ; j++) {
                        if(grid[i][j] == k) {    
                            change(i, j);
                        }
                    }
                }
            }
        }
 
        print();
    }
 
    private static void change(int x, int y) {
        int[] pos = new int[2]; // 가장 큰 숫자가 있는 칸의 위치
        int max = 0;
 
        for(int d = 0 ; d < 8 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if(inRange(nx, ny) && grid[nx][ny] > max) {
                max = grid[nx][ny];
                pos = new int[] {nx, ny};
            }
        }
 
        // swap
        int tmp = grid[pos[0]][pos[1]];
        grid[pos[0]][pos[1]] = grid[x][y];
        grid[x][y] = tmp;
 
        return;
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < N);
    }
 
    private static void print() {
        StringBuilder sb = new StringBuilder();
        for(int[] i : grid) {
            for(int j : i)
                sb.append(j + " ");
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
}

 

 

 

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

---

(참고)

✔ 코드트리