(Java) Programmers 삼각달팽이 (대각행렬, 삼각행렬 탐색)

- 목차

 

소개.

아래 링크는 "Programmers 삼각달팽이" 문제의 웹링크입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/68645

프로그래머스

 

 

문제 설명.

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

 

 

문제 분석.

삼각달팽이 문제는 행렬의 순차적인 탐색 능력을 필요로합니다.

BFS, DFS 와 같은 완전탐색보다 정해진 경로로의 탐색이 필요합니다.

현재 문제는 삼각형 형태를 취하는 대각행렬을 만들고,

대각행렬의 탐색을 수행해야합니다.

 

시작점은 (0, 0) 입니다.

그리고 삼각행렬의 형태는 아래와 같습니다.

 

n 이 6 인 삼각행렬입니다.

o x x x x x
o o x x x x
o o o x x x
o o o o x x
o o o o o x
o o o o o o

 

그리고 탐색법은 아래와 같습니다.

1. 가장 하단의 지점까지 downward 로 이동합니다.

2. 가장 하단 지점에서 right 로 이동합니다.

3. 가장 오른 하단의 이점에 도달한다면 좌측 상단 방향으로 대각이동을 합니다.

 

해당 탐색법을 코드로 작성하면 아래와 같습니다.

 

int curX;
int curY;

// 하단으로 이동 
curY++;
curX 그대로 유지 

// 우측으로 이동 
curY 그대로 유지
curX++;

// 대각선 이동 
curY--;
curX--;

문제 풀이.

1. boolean[][] visited 행렬을 사용하여 재방문을 방지합니다.

2. int[][] map 행렬을 사용하여 increment 되는 숫자들을 저장합니다.

 

class Solution {
  public int[] solution(int n) {
    int[] answer = new int[getMaxValue(n)];
    int[][] map = new int[n][n];
    boolean[][] visited =  new boolean[n][n];

    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        visited[i][j] = true;
      }
    }

    int value = 1;
    int curX = 0;
    int curY = 0;
    map[0][0] = 1;
    visited[0][0] = true;

    while (value < getMaxValue(n)) {

      // 좌측으로 이동
      while (curY + 1 < n && !visited[curY + 1][curX]) {
        curY++;
        visited[curY][curX] = true;
        value++;
        map[curY][curX] = value;
      }

      // 우측으로 이동
      while (curX + 1 < n && !visited[curY][curX + 1]) {
        curX++;
        visited[curY][curX] = true;
        value++;
        map[curY][curX] = value;
      }

      // 대각선 이동
      while (curY - 1 > 0 && curX - 1 > 0 && !visited[curY - 1][curX - 1]) {
        curY--;
        curX--;
        visited[curY][curX] = true;
        value++;
        map[curY][curX] = value;
      }
    }

    int counter = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= i; j++) {
        if (map[i][j] > 0) answer[counter++] = map[i][j];
      }
    }

    return answer;
  }

  // 삼각달팽이 행렬이 가질 수 있는 최대 숫자
  int getMaxValue(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
      sum += i;
    }
    return sum;
  }
}