[네번째 문제] 백준 / 1058 : 친구

solved.ac 기준으로 실버1문제를 푸는 중이고 ,
등급이 실버1이 되면 골드5문제로 넘어갈 예정이다.
( 실버1이 되지 않더라도 배움이 충분하다고 생각 되면 넘어간다)
현재 : 실버5

# include <iostream>


using namespace std;

char arrFriend[51][51];

// 2친구수를 구하려면 , 직접 친구이거나, 같이 아는 사람이 존재해야한다

//N Y N N -- > A는 B와는 친구지만 C , D와는 직접 친구가 아니다. 그러나 C ,A와 친구인 B가 있으므로 2친구수 +1 DA와친구인 B도 있으므로 2친구수 +2 
//Y N N N
//N N N Y
//N N Y N


// 50명 기준으로
// 연산은 50X50X50

int main() {
	int N;
	
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arrFriend[i][j];
		}
	}
	int maxi = 0;
	for (int i = 0; i < N; i++) {
		int fcnt = 0;
		for (int j = 0; j < N; j++) {
			if(arrFriend[i][j] == 'Y') fcnt += 1; // 직접친구
			else {
				for (int k = 0; k < N; k++) {
					if (arrFriend[k][j] == 'Y' && arrFriend[k][i] == 'Y' ) {
						fcnt += 1; // 다른친구와 나를 동시에 아는사람이 존재
						break;
					}
				}
			}
		}
		if (fcnt > maxi) maxi = fcnt;
	}
	if (maxi == 0) {
		cout << maxi;
	}
	else cout << maxi -1 ;
	return 0;
}

문제 자체는 직관적이었다.
삼중 for문의 경우 아름답지는 않지만 연산횟수가
50x50x50 = 125000회였기 때문에 지난번의 교훈을 벗삼아 쉽게 풀기로 했다.

여기서 치명적인 실수를 하게 되는데, 위와 같이 코드를 짜게 되면 본인 역시 2-친구로 인식하게 되어버려서 코드를 수정하기보다는 -1을 빼줘서 구하기로 했다.

그러나 테스트 케이스
2
NN
NN
의 경우 maxi 자체가 0이기 때문에 -1을 하면 안된다.

따라서 0인 경우를 else로 다시 처리해 줬지만,


if (i !=j && arrFriend[k][j] == 'Y' && arrFriend[k][i] == 'Y' ) 
		

위의 조건을 이렇게 바꿔주면 깔끔하게 해결 할 수 있다.

좋은 웹페이지 즐겨찾기