[SWEA] 1954. 달팽이 숫자

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PobmqAPoDFAUq&categoryId=AV5PobmqAPoDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=2

SW Expert Academy

---

#include<cstdio>
#include<iostream>
#include<stack>
#include<algorithm>

typedef long long ll;
using namespace std;
int mx[4]={0,1,0,-1};
int my[4]={1,0,-1,0};
// 그러면 right down left up 순서로 이동 
void dfs(int i,int num)
{
	stack< pair<int, int> > s;
	int x,y;
	int visited[10][10] ={0,};
	int board[10][10]={0,};
	int inc = 1;
	int d = 0;//direction , default : right
	int posx,posy;
	s.push({0,0});
	// right, down, left 
	while(!s.empty()) {
		x = s.top().first;
		y = s.top().second;
		s.pop();
		if(visited[x][y]) continue;
		else visited[x][y] = 1;
		board[x][y] = inc++;
		posx = x+mx[d];
		posy = y+my[d];
		
		if(posx >= 0 && posx < num && posy >=0 && posy < num && !visited[posx][posy]){
			s.push({posx,posy});
		}else{
			d++;
			if(d>3) d %=4;
			posx = x+mx[d];
			posy = y+my[d];
			if(posx >= 0 && posx < num && posy >=0 && posy < num && !visited[posx][posy])
				s.push({posx,posy});
		}
		
	}
	
	printf("#%d\n",i+1);
	for(int x = 0; x < num; x++)
	{
		for(int y = 0; y < num; y++)
		{
			printf("%d ",board[x][y]);
		}
		printf("\n");
	}
}
int main(void)
{
	int size;
	int num;
	
	
	scanf("%d",&size);
	for(int i = 0; i < size; i++)
	{
		scanf("%d",&num);
		dfs(i,num);
	}
	return 0;
}

---

 

문제해결 : dfs로 하려고 했는데 굳이? 라는 것도 있었고, 해보니까 방향의 우선순위를 정해줘야해서 구현이 안됐다.

 

시행착오 :

ex) right, down, left, up 순서로 가는걸 우선순위로 잡았다.

stack에 up left down right 순서로 넣었다.

3x3 까지는 운좋게 잘 됐다 하지만 4x4 부터 문제가 생긴다

대표사진 삭제

사진 설명을 입력하세요.

이런식으로 위로 올라갈때 right와 up이 비어있는데, right먼저 들어가버리는 결과가 나왔다.

이걸 어떻게 하지 하다가.. dfs로는 안되는것 같았다. 이건 말그대로 search니까..

 

그래서 visited 배열은 살리고..

direction = 0 -> right, 1 = > down, 2 => left, 3 => up 인덱스를 이용해서 움직이기로 했다.

그다음 이동하는건 일단 right를 쭉 가다가 범위를 벗어나면 방향을 바꾸는 식으로 했다.

 

visited가 왜 필요한가? 4x4에서 10에서 11 12 이렇게 위로 올라가게 되는데..

이때 visited가 없으면 1번 방문지까지 올라가게 되어버리기 때문이다.

 

깨달은것 :

1. bfs, dfs의 차이에 대해서 다시 생각해보게 되었음.

dfs = 한방향만 우직하게 파고나서 다시 돌아가서 다음방향 파기.. 직선맨

bfs = parallelism 느낌.. 모든방향 동시 진행

당연히 저런 속성때문에 큐와 스택이 어디에 필요한지도 자연스레 느낌.

 

2. 배열을 direction처럼 이용해서 부딪히면 방향바꾸고.. 이런 규칙성만 잘 발견하면 다른거에도 응용이 가능할 것 같다는 생각.

 

===END

보통 고민을 좀 해야 얻어가는게 많다.