일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 가가 형사 시리즈
- 웹 개발
- 동적 프로그래밍
- 정보 보안
- Django Rest Framework
- 백엔드
- 독서
- 웹 해킹
- 코딩 공부
- KITRI
- 백준
- Django Restful API
- 히가시노 게이고
- 코딩
- bob 9기 후기
- best of the best
- 코딩공부
- bob
- 추리 소설
- webhacking.kr
- 백준알고리즘
- 삼성 SW 역량 테스트
- 백엔드 개발
- serializer
- 일본 소설
- Blind SQL Injection
- 알고리즘
- DP
- 백준 알고리즘
- Django CRUD
- Today
- Total
요모조모 ʚɞ
[C] 백준 17070번 : 파이프 옮기기 1 본문
이번에는 백준에 있는 삼성 A형 기출문제를 풀어보았습니다! •ө•
문제집에 9문제? 정도 있었던 것 같은데, 제일 난이도가 낮은 것부터 하나씩 풀어보려고 합니다ㅎㅎ
.
이번 문제는 2단계에 걸쳐 문제를 풀어보았습니다.
1. 규칙을 찾아 일반화하기
2. 코드로 작성하기
https://www.acmicpc.net/problem/17070
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 변수를 전역으로 선언하고 사용하였는데 문제가 발생하였습니다.
( 이전 함수에서 계산되었던 값이 계속 들어있는 것 같더라구요ㅠ )
=> 전역 변수를 사용하지 말고 재귀 호출 시 인자를 하나하나 전달받도록 해줍니다.
-------------------------------------------------------------------------------------------------------------------
ㅎㅎ,, 코딩을 한동안 안 하다가 오랜만에 하다 보니
정말 기본적인 실수를 많이 하는 것 같습니다 ^^
이제 중간고사 과제 기간이라 슬슬 바쁠 것 같긴 한데 ㅜㅜ
시간을 쪼개서 더 열심히 풀어봐야겠습니다,, 흡
'코딩 > C' 카테고리의 다른 글
[C] 백준 13458번 시험 감독 (0) | 2020.10.12 |
---|---|
[C] 백준 17471번 : 게리맨더링 (0) | 2020.05.04 |
[C] 백준 1149번 : RGB거리 (0) | 2020.05.02 |
[C] 백준 2294번 : 동전 2 (0) | 2020.04.30 |
[C] 백준 1915번 : 가장 큰 정사각형 (0) | 2020.04.29 |