snail - swexpert 문제

📌 문제

🔥 1954번 달팽이 숫자
🔥 난이도 D2
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PobmqAPoDFAUq&categoryId=AV5PobmqAPoDFAUq&categoryType=CODE&problemTitle=%EB%8B%AC%ED%8C%BD%EC%9D%B4&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

안쪽으로 들어가는 모양으로 숫자가 형성된다.

 

ex) n = 3

1 2 3

8 9 4

7 6 5

 

이차원 배열의 값을 출력하라.

📌 해결 아이디어

🔥 이차원 배열에 순차적인 index의 값을 넣는 방법

for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
        arr[i][j] = i*N+j+1;
    }
}

직관적으로 생각하면 된다.

 

i가 한 줄을 의미하기 때문에 다음 줄로 바뀌면, N만큼의 값이 추가된 index로 바꾸어주어야 한다.

기본 시작 index라고 생각하면 될 것 같다.

거기에 열의 index가 증가할 때마다 = j+1 을 해주면 된다. 이 때, 배열에 넣는 값이 1부터 시작이므로 +1을 해준다.

int M = sc.nextInt();
int N = sc.nextInt();

int[][] arr = new int[M][N];

for(int i=0;i<M;i++){
    for(int j=0;j<N;j++){
        arr[i][j] = i*N+j+1;
    }
}

만약 N과 M의 값이 다르다면, 열의 값을 기준으로 i를 곱해준다. 즉, 열의 값만큼 시작 index를 정해주어야 하기 때문에 N을 곱해준다고 생각하면 된다.

🔥 방향

static int [] dx = {0,1,0,-1};
static int [] dy = {1,0,-1,0};

for(int i=0;i<N;i++){
	for(int j=0;j<N;j++){
    	map[a][b] = i*N+j+1;
        if( isOutOfMap( a + dx[direction] , b + dy[direction]) || map[ a + dx[direction] ] [ b + dy[direction] != 0){
        	direction = (direction+1)%4;
            }
        a += dx[direction];
        b += dy[direction];
       	...

배열의 크기만큼 모두 다 채워질 것이기 때문에 for loop 2번을 돌면 다 채워진다.

방향을 어떻게 설정하는가? 가 가장 어려운 부분인데, 이 부분은

• dx,dy
• check ( 위에서는 isOutOfMap )
• direction = (direction+1)%4 
• a += dx[direction]
• b += dy[direction]

등으로 표준화 된 풀이를 할 수 있다.

public class SnailSWExpert {

    public static int T;
    static int N;
    static int[][] map;

    // 우 하 좌 상
    static int [] dx = {0,1,0,-1};
    static int [] dy = {1,0,-1,0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();

        for(int t=1;t<=T;t++){
            N = sc.nextInt();
            map = new int[N][N];

            int a=0;
            int b=0;
            int direction = 0;

            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    map[a][b] = i*N+j+1;
                    int nx = a+dx[direction];
                    int ny = b+dy[direction];

                    if(isOutOfMap(nx,ny)|| map[nx][ny]!=0){
                        direction = (direction+1)%4;
                    }
                    // 방향이 바뀌었다면 바뀐대로 더해줘야 한다
                    //  a = nx;
                    //  b = ny;
                    a+= dx[direction];
                    b+= dy[direction];
                }
            }
            System.out.println(t + "번 답");
            print(map);
        }

    }

    public static boolean isOutOfMap(int nx, int ny){
        return nx < 0 || nx >= N || ny < 0 || ny >= N;
    }

    public static void print(int[][] arr){
        for(int i=0;i< arr.length;i++){
            for(int j=0;j<arr.length;j++){
                System.out.print(arr[i][j] + "   ");
            }
            System.out.println();
        }
    }
}

🔥 다시 풀 때 실수한 부분

int nx = a + dx[direction]
int ny = b + dy[direction]

if 방향을 벗어난다면:
	direction = (direction+1)%4

a = nx
b = ny
<---- 이렇게 하면 방향을 벗어났을 때 direction이 바뀌지 않는 것

📌 다시 풀기 21.12.14

package src.다시풀기.swea.달팽이;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

/**
 * date : 21.12.14
 */

public class Solution {

    static int T;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    static int d;
    static int[][] map;
    static boolean[][] visited;
    static int x,y;
    static int N;

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("./src/다시풀기/swea/달팽이/input.txt"));
        Scanner sc = new Scanner(System.in);

        T = sc.nextInt();

        for(int t=1;t<=T;t++){
            N = sc.nextInt();
            map = new int[N][N];
            visited = new boolean[N][N];
            d=0;
            x=0;
            y=0;

            int cnt = 1;

            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    map[x][y] = cnt++;
                    visited[x][y] = true;

                    int nx = x + dx[d];
                    int ny = y + dy[d];

                    if(isOut(nx,ny) || visited[nx][ny]){
                        d = (d+1)%4;
                        nx = x + dx[d];
                        ny = y + dy[d];
                    }
                    x = nx;
                    y = ny;
                }
            }
            System.out.println("#"+t);
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
        }
    }
    static boolean isOut(int nx,int ny){
        return nx < 0 || ny <0 || nx>=N || ny>=N;
    }
}