[C] 백준 17070번 : 파이프 옮기기 1

 

이번에는 백준에 있는 삼성 A형 기출문제를 풀어보았습니다!  •ө• 

문제집에 9문제? 정도 있었던 것 같은데, 제일 난이도가 낮은 것부터 하나씩 풀어보려고 합니다ㅎㅎ

.

이번 문제는 2단계에 걸쳐 문제를 풀어보았습니다.

1. 규칙을 찾아 일반화하기

2. 코드로 작성하기

 

백준 17070번

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

1. 규칙을 찾아 일반화하기

우선 문제에 주어진 설명을 꼼꼼하게 읽어보았습니다.

 

문제 설명

 

파이프가 가질 수 있는 상태로는 가로, 세로, 대각선 총 3가지가 있고,

각 상태에 따라 움직일 수 있는 방향이 달라집니다.

따라서 저는 이것을 상태별로 나누어 정리해보았습니다.

다음은 파이프 상태가 가로일 때, 세로일 때, 대각선일 때를 구분하여 정리한 그림입니다.

 

파이프 상태에 따른 이동

 

저는 이것을 통해 가로, 세로, 대각선 3방향으로 이동할 수 있는지를 판단하는 함수를 만들어야겠다고 생각했습니다.

그리고 파이프가 가로인지, 세로인지, 대각선인지를 파악하려면 시작점과 끝점 위치 또한 필요함을 느꼈습니다.

뿐만 아니라 파이프의 상태에 따라 이동할 수 있는 방향이 최소 2가지씩은 있기 때문에 재귀 호출을 쓰면 편할 것 같았습니다.

이렇게 규칙들을 대충 일반화 해본  후 이것을 코드로 작성해보았습니다.

 

-------------------------------------------------------------------------------------------------------------------

 

2. 코드로 작성하기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

// 변수 선언
typedef struct location {
	int x, y;
}loc;

int N;
int input[18][18];
int cnt = 0;

// 함수 선언
void width(loc, loc);
void height(loc, loc);
void diagonal(loc, loc);
void move(loc, loc);

int main() {

	loc start, end;
    
	// 초기화
	for (int i = 0; i <= 17; i++)
		for (int j = 0; j <= 17; j++)
			input[i][j] = -1;

	start.x = 1;
	start.y = 1;
	end.x = 1;
	end.y = 2;

	// 입력
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			scanf("%d", &input[i][j]);

	// move 함수 호출
	move(start, end);

	// 출력
	printf("%d", cnt);

	return 0;
}

void width(loc start, loc end) {
	int x = end.x;
	int y = end.y;
	// 가로로 이동 가능?
	if (input[x][y + 1] == 0) {
		start = end;
		end.y++;
		move(start, end);
	}
	return;
}
void height(loc start, loc end) {
	int x = end.x;
	int y = end.y;
	// 세로로 이동 가능?
	if (input[x + 1][y] == 0) {
		start = end;
		end.x++;
		move(start, end);
	}
	return;
}
void diagonal(loc start, loc end) {
	int x = end.x;
	int y = end.y;
	// 대각선으로 이동 가능?
	if (input[x][y + 1] == 0 && input[x + 1][y] == 0 && input[x + 1][y + 1] == 0) {
		start = end;
		end.x++;
		end.y++;
		move(start, end);
	}
	return;
}
void move(loc start, loc end) {

	if (end.x == N && end.y == N) {
		cnt++;
		return;
	}

	if (start.x == end.x) {
		width(start, end);
		diagonal(start, end);
	}
	else if (start.y == end.y) {
		height(start, end);
		diagonal(start, end);
	}
	else {
		width(start, end);
		height(start, end);
		diagonal(start, end);
	}
}

위의 코드는 제가 작성한 코드입니다.

우선 저는 좌표를 사용해야 하기 때문에 location이라는 구조체를 사용해주었습니다.

또한 코드 맨 밑의 move 함수를 통해 각 파이프의 상태를 구분한 후,

각 상태에 맞게 움직이기 위해 3가지 함수를 더 선언하였습니다.

width( ) -> 가로로 움직일 수 있는지 확인하고 움직인다. + 다시 move( ) 호출

height( ) -> 세로로 움직일 수 있는지 확인하고 움직인다. + 다시 move( ) 호출

diagonal( ) -> 대각선으로 움직일 수 있는지 확인하고 움직인다. + 다시 move( ) 호출

그리고 움직일 때는 파이프의 끝 점이었던 end를 다시 start로 만들어줍니다. (한 칸 움직이는 거니깐)

마지막으로 움직이는 방향에 맞게 end 값만 다시 설정해주면 됩니다.

.

다음과 같이 코드를 작성할 때는 ※주의할 점※이 몇 가지 있습니다.

 

① 함수 안에서 함수를 호출할 때는 함수 정의 주의하기

저는 보통 함수를 main 함수 위에서 선언하고 정의해주는 경우가 많은데,

이와 같이 코드를 작성하면 컴파일 에러가 나올 수 있습니다.

제가 작성한 기존 코드의 경우에는 width 함수가 위에 move 함수보다 먼저 선언되어 있는데,

 width 함수 내부에서 move 함수를 호출하였기 때문에 문제가 발생하였습니다.

=> 함수를 먼저 다 선언해준 후, main 함수 아래에서 함수를 정의해줍니다.

 

② 재귀 호출 사용 시 전역 변수 조심하기

저는 전역 변수 쓰는 걸 선호해서,, 안 좋은 건 다 갖췄네

함수 인자를 전역 변수로 선언하는 경우가 많습니다.

이번 문제에서도 함수 인자를 하나하나 넘겨주기가 귀찮아서

loc start와 loc end 변수를 전역으로 선언하고 사용하였는데 문제가 발생하였습니다.

( 이전 함수에서 계산되었던 값이 계속 들어있는 것 같더라구요ㅠ )

=> 전역 변수를 사용하지 말고 재귀 호출 시 인자를 하나하나 전달받도록 해줍니다.

 

-------------------------------------------------------------------------------------------------------------------

 

ㅎㅎ,, 코딩을 한동안 안 하다가 오랜만에 하다 보니

정말 기본적인 실수를 많이 하는 것 같습니다 ^^

이제 중간고사 과제 기간이라 슬슬 바쁠 것 같긴 한데 ㅜㅜ

시간을 쪼개서 더 열심히 풀어봐야겠습니다,, 흡