SWEA 1954. 달팽이 숫자 [D2] - java

SW Expert Academy

SW Expert Academy

---

달팽이 숫자 알고리즘은 배열에 들어가는 수가 달팽이 껍질같이 배열에 숫자를 채워 나간다.

 

1	2	3	4
12	13	14	5
11	17	15	6
10	9	8	7

 

이미지(표)로 봤을 때는 이해하기 쉽다. 하지만 진행방식에 대해서 구체적인 설명을 할 수 있을 정도로

로직을 파악하는 것이 중요하다.

 

일단 이 방법이 어떻게 진행되나 머리속으로 생각해야한다.

 

---

 

로직은 다음과 같이 생각할 수 있다.

 

• 알고리즘은 한 배열의 출발점부터 한 방향으로 진행한다.
• 한 방향으로 진행하는데 다음 목적지가 (1) 배열 범위를 벗어나거나 (2) 이미 다른값이 채워졌으면 방향을 바꾸어 다음 목적지를 변경한다.
• 이를 숫자가 다 채워질 때 까지 반복한다. (배열 size * 배열 size 만큼)

 

"방향" 이라는 키워드를 통해 알고리즘을 구현할 수 있어야한다.

 

 

 

"방향" 이 들어간 알고리즘들은 다음과 같은 변수들을 사용하는 것이 좋다

 

drow = {상, 하 , 좌, 우};

dcol = {상, 하 , 좌, 우};

direction = 0;

 

dx 와 dy 는 가고자 하는 방향에 따라 움직일 수 있는 좌표를 제공한다.

 

direction 은 어느방향으로 진행할지 알려주는 변수로 사용한다. 

 

방향은 dx[direction], dy[direction] 으로 정할 수 있다.

 

예시로 위로부터 시계방향으로 방향을 전환하고 싶다고 하면 다음과 같이 코드를 적을 수 있다.

 

 

 

currentRow = 0;
currentCol = 0;

drow = {-1, 0 , 1, 0} // 12시(위쪽), 3시(오른쪽), 6시(아래쪽), 9시(왼쪽) 

dcol = {0, 1 , 0, -1} // 12시(위쪽), 3시(오른쪽), 6시(아래쪽), 9시(왼쪽) 

direction = 0;

for (inti=0; i<16; i++){
    currentRow = currentRow + drow[direction]; // 행이동
    currentCol = currentCol + dcol[direction]; // 열이동
    direction = (direction + 1) % 4; // 시계방향으로 계속 돌 수 있도록 나머지 연산자 사용
}

 

 

 

 

로직을 어떻게 이해할 것인가에 대해서는 직접 그려보는 것이 직관적이다.

 

한 방향으로 진행하지만 진행하는데 있어 다음 목적지가 배열 밖의 범위거나 다른값이 채워진 상태면

그 방향으로 가지 못한다. 그런 경우에는 다른 방향으로 다음목적지를 변경해야한다.

 

---

 

이는 바로 알고리즘의 조건절이 된다.

 

다음 목적지가 배열밖이거나 다른값이 있는 상태일 때 방향을 바꿔서 이동한다.

 

 

 

1. 다음 목적지(nextRow, nextCol) 가 배열범위 밖인가?

boolean exceedArrayIndex = 
nextRow < 0 || nextCol < 0 || nextRow >= array.length || nextCol >= array.length

 

2. 이미 다른 값이 채워진 상태인가?

* int 배열초기화 시 초기값이 0이므로 0이 아닌 배열값은 이미 알고리즘이 진행된 곳이다.

boolean checkOtherValue =
arr[nextRow][nextCol] > 0

 

3. 다른 방향으로 변경한다(다음목적지를 변경한다)

direction = (direction +1) % 4; // 방향바꾸기
nextRow = currentRow + drow[direction]; // 다음목적지 변경 (행방향)
nextCol = currentCol + dcol[direction]; // 다음목적지 변경 (열방향)

---

 

< 조건절 합치기 >

if ( nextRow < 0 || nextCol < 0 || nextRow >= array.length || nextCol >= array.length || (snale[nextRow][nextCol] != 0)) {
    direction = (direction +1) % 4;
    nextRow = row + dr[direction]; // 다음목적지 바꾸기
    nextCol = col + dc[direction];
}

 

---

 

 

정리.

 

1. 숫자가 다 채워질때까지 진행한다 ( 배열 size * 배열 size) 

2. 다음 목적지가 배열 범위 밖이거나 이미 값이 있는 경우 다른 방향으로 변경하여 다음목적지를 변경한다.

3. 현재 목적지에 값을 넣어주고 다음 목적지로 이동한다.

 

 

[전체코드]

int size = sc.nextInt();
int[][] snale = new int[size][size];
int direction = 0;
int row = 0; // 처음위치는 (0,0)
int col = 0;
int nextRow = 0;
int nextCol = 0;
int number = 1;
while (number <= (size * size)){
    nextRow = row + dr[direction]; // 다음 목적지
    nextCol = col + dc[direction];
    if ( nextRow < 0 || nextCol < 0 || nextRow >= size || nextCol >= size || (snale[nextRow][nextCol] != 0)) { // 조건절
        direction = (direction +1) % 4;
        nextRow = row + dr[direction]; // 다음목적지 바꾸기
        nextCol = col + dc[direction];
    } 
    snale[row][col] = number++; // 목적지 출발 전 현재 위치 값 채우기
    row = nextRow; // 목적지 도착(이동)
    col = nextCol; 
}