[C++] 백준 15685번 드래곤 커브

15685번: 드래곤 커브

구현 / 시뮬레이션 문제.

삼성 SW에도 나왔다고 하는 문제다.

정답률이 높아서 풀어봤는데 마지막에 좌표를 이상하게 설정해서 틀렸었다.

좌표가 0부터 100까지인데 1부터 100까지만 고려해서 틀렸었다.

(컴공은 1이 시작이 아니라 0부터 시작인데, 난 컴공이 아닌가보다;)

 

문제풀이

 

입력은 X좌표, Y좌표 순서이고, 각 방향에 따라 이미 숫자를 준다.

0 : 우

1 : 상

2 : 좌

3 : 하

3 3 3 0 1 4 2 1 3 4 2 2 1

1번 테스트 케이스를 예시로 들어보자.

1. (3, 3)에서 0, 맨 처음 오른쪽 방향으로 1세대 드래곤 커브를 생성한다.

(3, 3)	(3, 4)

가 0세대의 드래곤 커브이고, 오른쪽 방향(0)으로 이동했다.

	(2, 4)
(3, 3)	(3, 4)

가 1세대 드래곤 커브가 될 것이다. 이는 전에 있던 끝점에서 위방향(1)로 이동했다.

 

2. (2, 4)에서 1, 맨 처음 위 방향으로 3세대 드래곤 커브를 생성한다.

				(1, 4)
				(2, 4)

가 0세대의 드래곤 커브이고, 위 방향(1)로 이동했다.

			(1, 3)	(1, 4)
				(2, 4)

가 1세대의 드래곤 커브가 된다. 좌 방향(2)로 이동했다.

			(1, 3)	(1, 4)
		(2, 2)	(2, 3)	(2, 4)

가 2세대의 드래곤 커브이다. 순차적으로 아래 방향(3), 좌 방향(2)로 이동했다.

 

여기서 규칙을 찾았다.

끝 점에서 추가 세대를 붙이는 드래곤 커브는,

이전 세대에서 가지고 있던 선분(방향)을 마지막 순번부터 그 다음 방향들로 이동시켜주면 된다.

말로 설명하자니 어려운데,

만일 3세대 드래곤 커브를 생성할 때, 2세대에서 방향이

[위(1), 좌(2), 하(3), 좌(2)]의 방향이 있었다면 마지막부터

1. (2 + 1) % 4 = 3, 하 방향 이동하고 하 방향 저장

2. (3 + 1) % 4 = 0, 우 방향 이동하고 우 방향 저장

3. (2 + 1) % 4 = 3, 하 방향 이동하고 하 방향 저장

4. (1 + 1) % 4 = 2, 좌 방향 이동하고 좌 방향 저장

3, 0, 3, 2의 순서대로 이동했으므로,

 

지나온 방향에는 [1, 2, 3, 2, 3, 0, 3, 2]의 방향이 존재하게 된다.

 

이를 세대가 완성될 때까지 진행시켜 주면된다.

 

코드로 살펴보자.

사용한 변수와 STL

• dragonCurveCnt : 드래곤 커브의 횟수
• curX, curY, startDirection, generation : 각 드래곤 커브마다 입력받는 정보, X좌표, Y좌표, 시작방향, 세대
• board 배열 : 각 좌표가 드래곤 커브가 지나간 곳인지 아닌지를 저장하는 배열
• direction 배열 : 이동하는 방향. 문제의 조건에 맞게 구현했다.
• dragonCurveVec 벡터 : 현재 드래곤 커브의 i세대가 지나온 방향들을 저장해놓는 벡터
• ans : 출력값.

 

메인함수

처음에 드래곤 커브의 횟수를 입력받고, 드래곤 커브의 정보를 입력받는다.

이 때 입력받기 전, 이전에 진행했던 드래곤 커브의 방향은 지워주어야 하므로 dragonCurVec을 Clear()로 초기화해준다.

그리고 입력받은 정보로 makeDragonCurve메서드로 0세대 드래곤커브부터 만들어준다.

마지막으로 모든 좌표에 대해 1x1정사각형의 모든 좌표에 대해 드래곤 커브가 지나간 곳인지 체크해준다.

맞다면 ans에 + 1을 해준다.

 

드래곤 커브 메서드

드래곤 커브를 진행하는 메서드이다.

0세대 드래곤 커브라면, 현재 좌표를 드래곤 커브가 지나간 곳으로 만들어주고,

시작 방향에 대해 현재 좌표를 이동시킨다. 그리고 이동시킨 좌표도 드래곤 커브가 지나간 곳으로 만들어준다.

그리고 시작 방향을 방향을 저장해두는 벡터인 dragonCurveVec 벡터에 넣어주고, 1세대 드래곤 커브를 만들어준다.

 

0세대가 아니라면, 저장중인 방향들에 대해서 지나온 마지막 방향부터 (방향 + 1) % 4를 해주며, 좌표를 이동시켜준다.

그리고 이동시킨 좌표에 대해 드래곤 커브가 지나온 곳으로 만들어주고, 현재 지난 방향을 벡터에 저장시켜 넣는다.

처음에는 이렇게 하면, 벡터에 계속 집어넣게 돼서 무한루프가 되는게 아닐까 생각했는데,

어차피 반복문의 시작이 size() - 1로, 지나온 방향들에 대해서만 고려하게 되므로 상관없었다.

모든 방향을 지났다면 그 다음 세대의 드래곤 커브를 만든다.

 

만일 입력받은 세대보다 현재 만들려는 idx가 높다면 return한다.

사각형의 좌표가 모두 드래곤 커브가 지나간 곳인지 체크하는 메서드

findSquareCnt가 찾아주는 메서드이다.

시작좌표(i, j)	(i, j +1 1)
(i + 1, j)	(i + 1, j + 1)

위 같은 형태로 체크하게 된다.

 

좌표를 0부터가 아니라 1부터 고려해주어서 계속 틀렸었다.

쉬운 문제였었는지, 반례도 없었다.

다음 번 부터는 좀 더 꼼꼼히 체크해야겠다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.