[C] 백준 14467번 소가 길을 건너간 이유 1

1. 문제이해

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

14467번: 소가 길을 건너간 이유 1

 

관찰 횟수와 각 소의 번호와 위치를 입력받아,

소가 길을 건너간 최소 횟수를 출력하는 알고리즘을 구현하는 것이 목표이다.

몇 번 소가 몇 번 위치를 바꾼것인지를 모두 더한 것이 소가 길을 건너간 최소 횟수이다. 

 

 

 

2. 문제풀이

 

이번에도 문제를 잘못 이해해서 코드를 두번짜는 일이 발생했다..

처음에는 위치를 바꾼 소들 중에서, 가장 많이 위치를 옮겨간 소의 횟수를 출력하는 것으로 이해했다.

코드를 구현하고 테스트를 해보고, 잘못한 게 없는데.. 하고 한참을 찾다가 힌트를 보고 아차 싶었다.

 

문제에서 원하는 것은 몇 번 소가 몇 번 위치를 바꾼것인지를 모두 더한 것(=최소횟수)이었다.

따라서, 예제 입력 1에서 확인할 수 있듯이, 3번 소의 위치는 1-0-0-1 이므로, 결국 1-0-1 2번 위치를 옮긴것이다.

또한, 4번 소의 위치도 1-0으로, 1번 위치를 옮긴것이 확인된다.

따라서, 두 소의 옮긴 횟수를 더한 '3번'을 출력해주면, 이것이 소가 길을 건너간 최소 횟수가 된다.

 

이런 식으로, 각 소의 위치를 확인하고, 소의 위치가 달라진 것이 확인 되면 체크하여,

체크 값들의 합계를 출력하는 식으로 구현했다.

 

 

 

3. 소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {

	int count;  // 관찰 횟수
	int cow[100][2];  // 입력한 소의 번호와 위치
	int countcow[100];  // 각 소가 건너간 횟수
	int check[100];  // 각 소의 마지막 위치 체크
	int i, j;  // i는 소, j는 위치
	int min = 0;  // 길을 건너간 최소 횟수

	// 관찰 횟수와 소의 번호와 위치들을 입력받음
	scanf("%d", &count);

	for (i = 0; i < count; i++) {
		scanf("%d %d", &cow[i][0], &cow[i][1]);
	}

	/* 각 소들의 위치와 옮긴 횟수 초기화
	마지막 위치 체크값을 0으로 하면, 
	아래 과정에서 제대로 체크못하므로 -1로 설정 */
	for (i = 0; i < count; i++) {
		countcow[i] = 0;
		check[i] = -1;
	}

	for (i = 0; i < count; i++) {
		for (j = i+1; j < count; j++) {
			// 동일한 소인지 확인하고, 위치가 다르고, 마지막 위치와도 다를 때
			if ((cow[i][0] == cow[j][0]) && (cow[i][1] != cow[j][1]) 
				&& (cow[j][1] != check[cow[i][0]])) {
            		// 해당 소의 건너간 횟수++
				countcow[cow[i][0]]++;
            		// 해당 소의 위치 마지막 초기화 (0또는 1)
				check[cow[i][0]] = cow[j][1];
				break;
			}
		}
	}

	// 소의 건너간 횟수들을 모두 다 더함
	for (int i = 0; i < count-1; i++) {
		min += countcow[i];
	}

	printf("%d", min);

}

구현하는게 생각보다 힘들었다.

동일한 소인지 확인하고, 소의 위치가 바뀌었는지 확인하고,  이미 확인한 위치라면 고려해주지 않아야 하니,

개인적으로 생각보다 구현하기 까다로운 점들이 몇군데 있었다.

글을 쓰고 난 뒤에 다른 좋은 방법들이 있는지 몇차례 찾아볼 예정이다. 😅

 

우선, 관찰 횟수를 입력받고 해당 횟수만큼 관찰한 소의 번호, 위치를 이차원 배열을 통해 입력받았다.

이후 countcow, check라는 일차원 배열을 두고, 각각 0과 -1로 초기화 해주었다.

여기서 check는 위치가 바뀌었는지를 체크하는 변수로,

밑의 for문에서 조건들을 만족하고, check값이 다를 경우에만 소의 위치가 바뀌었다고 해주었다.

 

처음 코드를 짤 때, 이 check부분을 0으로 모두 초기화 해주어서 원하는 결괏값이 계속 나오지 않았는데, 

이는 위치 부분이 모두 0과 1로 나타나기때문에, 초기값을 0으로 설정해주면,

소의 위치가 1인데도 0부터 시작하는 경우가 있어 원하는 값이 나오지 않았던 것이었다.

 

countcow 변수는, for문에서 각 소의 위치가 바뀌면, 해당 소가 몇 번 위치를 바꾸었는지 횟수를 저장하는 변수로,

차후에 모두 더해주어야 하기때문에 0으로 초기화 해주었다.

 

이후 이중 for문을 통해,

1. 동일한 소인지 확인하고,

2. 위치가 변했는지 확인하고,

3. 마지막으로 저장된 위치와 다른지 확인

세가지 조건이 모두 충족되면 소가 위치를 바꾸었다고 확인,

해당 소의 번호에 해당하는 countcow 변수를 증감시키고, 위치를 초기화해주었다.

for문이 종료되면, countcow 변수에 저장된 값들을 차례로 더해주고, 이를 출력했다.

 

 

---

요즘들어 문제를 잘못읽어 코드를 여러번 짜거나 하는 일이 계속 있는것같다..😱

하루빨리 이런 습관은 고치고 문제를 제대로 파악한 후에 코드를 작성하는 습관을 들여야겠다.

이 문제도 힌트가 없었으면 계속 왜 틀렸다고 그러지... 하고 하루종일 붙잡고 있었을지도 모르겠다..ㅎㅎ

내일은 하루 쉬고, 월요일부터 다시 시작하고, 파이썬 공부도 해야지.😋