level2_삼각달팽이

문제

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

코딩테스트 연습 - 삼각 달팽이

---

접근방법

1) 접근 사고

인덱스값을 조절해주면 해결하면 됩니다. 탐색시 방문한 곳을 또 방문해주면 반복문을 탈출하게 설정해주었습니다.

 

2) 시간 복잡도

O(n^2)

 

3) 실수

 

4) 배운점

 

5) PS

 

---

정답 코드

#include <bits/stdc++.h>

using namespace std;
const int MAX = 1001;
int board[MAX][MAX];
bool visited[MAX][MAX];
bool isValid(int y, int x, int n){
	return y >= 0 && y < n && x >= 0 && x < n;
}

vector<int> solution(int n){
	vector<int> answer;
    if(n == 1){
        answer.push_back(1);
        return answer;
    }

	int N = n; int cnt = 1;
	int sY = 0;
	int sX = 0;
	while (1){
		if (!isValid(sY, sX, n) || sY == n - 1)
			break;

		for (int i = sY; i < N; i++){
			if (visited[i][sX])
				break;

			board[i][sX] = cnt, cnt++;
			visited[i][sX] = true;
		}
		int j;
		int jcnt = 0;
		for (j = sX + 1; j < N; j++){
			if (visited[N - 1][j])
			{
				break;
			}
			board[N - 1][j] = cnt, cnt++;
			visited[n - 1][j] = true;
		}
		j;
		for (int k = 1; k < N - 1; k++){
			if (visited[N - 1 - k][j - 1 - k]){
				break;
			}

			board[N - 1 - k][j - 1 - k] = cnt, cnt++;
			visited[N - 1 - k][j - 1 - k] = true;
		}
		sY += 2; sX += 1;
		N--;
	}

	for (int i = 0; i < n; i++){
		for (int j = 0; j <= i; j++){
			answer.push_back(board[i][j]);
		}
		cout << "\n";
	}
	return answer;
}

int main(){
	vector<int> a = solution(10);
	
}