이것 저것 &

문제링크: https://www.acmicpc.net/problem/1389

6다리면 건너면 세상사람들을 다 알 수 있다~ 이런 느낌의 문제였습니다.

당연히 탐색이라면 dfs, bfs를 먼저 생각하셔야 합니다.  문제 조건으로 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)입니다. 비교적 큰 수이기 때문에 dfs보다는 bfs를 먼저 생각했습니다. 

각각의 n번에서 최적탐색을 통해서 가장 빨리 도달하는 관계의 합을 더해주면 되는 방식이였습니다.

정답코드입니다.  bfs코드이고 4ms 정도의 시간이 걸립니다. 풀면서도 살짝 긴가민가 했습니다.

왜냐하면 O(n*m*n*큐)이고  대략 50,000,000 이상의 반복연산을 하기때문입니다. 1억번에는 훨씬 못미치지만 반복을 재외한 큐이므로 큐자체도 100번은 반복하지 않을까하는 생각때문입니다.

다행히 문제는 통과했습니다. ( 1초에 1억번이라는게 정확한 연산은 아니기도 하고 큐에 대해서 제가 놓치고 있는 부분이 있기에 통과된것같습니다.)

#include <iostream>
#include <cstring>
using namespace std;

int n = 0, m = 0;
int arr[5001][2];
int visited[5001];
int result = 1000000000,result_index =-1;
int bfs(int num) {
	int val = 0;
	int que[5000];
	
	for (int i = 1; i <= n; i++) {
		if (num == i) continue;
		memset(que, 0, 5000);
		memset(visited, 0, 5001);
		int started = 0, ended = 0;

		que[ended++] = num;
		visited[num] = 1;
		while (ended != started) {
			int a = que[started++];
			if (a == i) {
				val += visited[a] - 1;
				break;
			}
			for (int j = 0; j < m; j++) {
				if (arr[j][0] == a && !visited[arr[j][1]]) {
					que[ended++] = arr[j][1];
					visited[arr[j][1]] = visited[a] + 1;
				}
				else if (arr[j][1] == a && !visited[arr[j][0]]) {
					que[ended++] = arr[j][0];
					visited[arr[j][0]] = visited[a] + 1;
				}
			}
			

		}
	}

	return val;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> arr[i][0] >> arr[i][1];


	for (int i = 1; i <= n; i++) { //1~n번까지의 경로를 탐색
		int val = bfs(i);
		if (result > val) result = val, result_index = i;
	}
	cout << result_index << endl;
}

근데 생각해보니 더욱 효율적인 방법이 있었습니다. 

굳이 bfs문에서 n번 반복해줄 필요가 없었습니다...

어차피 while문이 한번다 돌고나면 visited엔 모든 인덱스별 최단경로값이 들어가있게 됩니다. 

친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다.

이 문제조건 때문입니다.

수정코드입니다.

시간도 0ms로 줄었습니다. 

#include <iostream>
#include <cstring>
using namespace std;

int n = 0, m = 0;
int arr[5001][2];
int visited[5001];
int result = 1000000000,result_index =-1;
int bfs(int num) {
	int val = 0;
	int que[5000];


	memset(que, 0, 5000);
	memset(visited, 0, 5001);
	int started = 0, ended = 0;

	que[ended++] = num;
	visited[num] = 1;
	while (ended != started) {
		int a = que[started++];

		for (int j = 0; j < m; j++) {
			if (arr[j][0] == a && !visited[arr[j][1]]) {
				que[ended++] = arr[j][1];
				visited[arr[j][1]] = visited[a] + 1;
			}
			else if (arr[j][1] == a && !visited[arr[j][0]]) {
				que[ended++] = arr[j][0];
				visited[arr[j][0]] = visited[a] + 1;
			}
		}

	}

	for (int i = 1; i <= n; i++)
		val += visited[i] - 1;


	return val;
	
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> arr[i][0] >> arr[i][1];


	for (int i = 1; i <= n; i++) { //1~n번까지의 경로를 탐색
		int val = bfs(i);
		if (result > val) result = val, result_index = i;
	}
	cout << result_index << endl;
}

dfs코드입니다. 다른 분의 코드를 참고해서 만들었습니다. 216ms로 시간이 오래걸립니다. 어느 것이 더욱 좋다 이 것보다는 자기한테 편한코드로 ac를 받으면 되는거라고 생각합니다. dfs의 장점은 명료하고 직관적이라는 것입니다. 다음뻔에는 dfs로 풀어야하는 문제를 리뷰하겠습니다. 모두 화이팅 :) 

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 102
#define INF 987654321
using namespace std;

int n,m;
int a,b;
int ans,res,step;
int person;

bool check[MAX];
vector<int> v[MAX];

void dfs(int ind,int goal,int cnt){
    if(ind == goal){
        step = min(step,cnt);
        return;
    }
    for(int i=0; i<v[ind].size(); i++){
        if(!check[v[ind][i]]){
            check[ind] = true;
            dfs(v[ind][i],goal,cnt+1);
            check[ind] = false;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    // 탐색
    ans = INF;
    for(int i=1; i<=n; i++){
        memset(check, false, sizeof(check));
        res = 0;
        for(int j=1; j<=n; j++){
            step = INF;
            if(i==j) continue;
            else{
                dfs(i,j,0);
                res += step;
            }
        }
        // 최소인지 검사
        if(ans > res){
            ans = res;
            person = i;
        }else if(ans == res){
            person = min(person, i);
        }
    }
    cout << person << endl;
}

문제링크:https://www.acmicpc.net/problem/3020

정렬문제입니다.

우선 일반적으로 생각할 수 있는 nXh 번 반복하여 값을 구하는 결과는 오답입니다. (시간초과)

O(n*h) = 200000 X 500000 번 반복하게 됩니다. 대략 1억번 반복에 1초라고 가정할때 당연한 결과 입니다.

완전탐색이 안된다면 고려해야할 것은 dp 혹은 그리디적 관점입니다. dp를 사용하기에는 결과값들 사이에 연관이 전혀 없습니다. 

정렬을 하고 결과값을 구할때 O(n)의 과정을 O(lgn)으로 줄일 수 있습니다. 

그방법은 이분탐색의 개념을 이용하는 것입니다. 정렬되어있는 상태라면 해당 높이를 기준으로 더큰 값들이 몇개 있는지 작은 값들이 몇개있는지 판단하는데 있어 평균적으로 lgn번의 탐색으로 값을 알 수 있습니다. 

직접구현해도 좋지만 C++의 lowerbound, upperbound를 사용해보겠습니다. 

사용 예시입니다. 선행조건은 꼭 정렬되어있는 배열을 넣어야합니다.

int val = lower_bound(arr, arr + n, num ) - arr ;
int val = upper_bound(arr, arr + n, num ) - arr ;

위처럼 사용하고 lower_bound는 arr배열의 0~n까지중  num값인덱스 중 제일 작은 값을 반환 합니다. 

upper_bound는 arr배열의 0~n까지중 num보다 큰 가장작은 값의 인덱스 값을 반환합니다.

즉 1 2 3 3 3 3 4 배열에서 num=2인 lowerbound는 1을 반환, upperbound는 2를 반환하는 형태입니다.

정답코드입니다. 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100001] = { 0 };
int arr2[100001] = { 0 };
int n, h;
int result = 200001, result_cnt = 0;


int main() {
	cin >> n >> h;

	for (int i = 0; i < n/2; i++) 
		cin >> arr[i ] >> arr2[i];
		
	sort(arr, arr + (n / 2));
	sort(arr2, arr2 + (n / 2));


	for (int i = 1; i <= h; i++) {

		int val = lower_bound(arr, arr + (n / 2), i ) - arr ;
		val += upper_bound(arr2, arr2 + (n / 2), h-i ) - arr2 ;
		val = n - val;

		if (result == val)
			result_cnt++;
		else if (result > val) { 
			result = val;
			result_cnt = 1;
		}
	}

	cout << result << ' ' << result_cnt << endl;

}

문제링크: https://www.acmicpc.net/problem/2225

생각하는 과정이 필요한 문제였습니다. 각각의 결과값들을 순차대로 구하다 보면 규칙을 찾을 수 있습니다.

점화식만 구하면 쉽게 구현할 수 있는 문제였습니다.

n = 5 k = 4 의 예제를 살펴보겠습니다.

dp[k]은 dp[k][0] ~ dp[k][n]의 합이 됩니다. 그리고 각각의 dp[k][i] 는 dp[k-1][i] ~ dp[k-1][n] 까지의 합이 됩니다. 

비교적 쉽게 점화식을 구할 수 있습니다. 

그래서 ex) 5 4의 결과값은 21+15+10+6+3+1 = ? 이 되겠죠 ㅎㅎ

그다음으로 주의하셔야 할 것은 %연산을 해주는 위치와 숫자 범위입니다. 매번 dp[k-1][i] ~ dp[k-1][n] 의 연산마다 %1000000000연산을 해줘도 해당문제에서는 상관없습니다. 하지만 조금더 컴팩트 하게 코딩하기 위해서 dp[k][i] 에서만 %1000000000연산을 해주고 싶었습니다. 

근데 만약 dp[k-1] 의 합이 다 10^9를 초과해서 오버플로우가 난다면, 에러가 날 수 밖에 없습니다. 그래서 long long 을 사용해서 배열을 구현했습니다.

아래는 정답코드입니다. :) 직접 표를 작성해보시고 점화식을 시그마형태로 구하고 구현해보세요! 화이팅

#include <iostream>
using namespace std;
long long dp[202][202] = { 0 };
int n, k;
long long result = 0;

int main() {
	cin >> n >> k;
	dp[1][n] = 1; // 초기값 설정
	for (int i = 1; i <= k; i++) {		
		for (int j = 0; j <= n; j++) {
			for (int u = j; u <= n; u++)
				dp[i][j] += dp[i - 1][u];
			dp[i][j] %= 1000000000;
		}
	}
	
	for (int i = 0; i <= n; i++)
		result += dp[k][i];
	result %= 1000000000;
	cout << result << endl;
}

문제링크:https://www.acmicpc.net/problem/11722

전형적인 LIS 문제였습니다. 

LIS 개념을 아신다면 어렵지 않은 문제였습니다.

그나마 주의해야 할 점은 이전 dp값을 전부 확인해봐야한다는 것입니다. 

바로 이전의 자신보다 큰값만 비교할 경우 예외가 발생합니다. 

Ex) 5

     10 5 4 6 3

정답코드입니다. 화이팅 :)

#include <iostream>
using namespace std;
int dp[1001] = { 0 };
int arr[1001] = { 0 };
int n,num,result =0;
int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		int maxed = 0;
		cin >> arr[i];
		for (int j = 0; j < i; j++) {
			if (arr[i] < arr[j] && maxed < dp[j])
				maxed = dp[j];
		}
		dp[i] = maxed + 1;
	}
	
	for (int i = 0; i < n; i++) {
		if (result < dp[i]) result = dp[i];
	}
	cout << result << endl;
}

null , 중복제거 sql 문 

SELECT  count( distinct NAME) from ANIMAL_INS  where NAME is not null ;

GROUP BY 

• 고양이와 개는 몇 마리 있을까

동물 보호소에 들어온 동물 중 고양이와 개가 각각 몇 마리인지 조회하는 SQL문을 작성해주세요. 이때 고양이가 개보다 먼저 조회해주세요.

SELECT ANIMAL_TYPE, COUNT(ANIMAL_TYPE) AS COUNT
FROM ANIMAL_INS
GROUP BY ANIMAL_TYPE

• 동명 동물 수 찾기

동물 보호소에 들어온 동물 이름 중 두 번 이상 쓰인 이름과 해당 이름이 쓰인 횟수를 조회하는 SQL문을 작성해주세요. 이때 결과는 이름이 없는 동물은 집계에서 제외하며, 결과는 이름 순으로 조회해주세요.

-- 코드를 입력하세요
SELECT name, count(name) as count from ANIMAL_INS
where name is not null 
group by  name having count(name) > 1

• 입양 시각 구하기(1)

보호소에서는 몇 시에 입양이 가장 활발하게 일어나는지 알아보려 합니다. 9시부터 19시까지, 각 시간대별로 입양이 몇 건이나 발생했는지 조회하는 SQL문을 작성해주세요. 이때 결과는 시간대 순으로 정렬해야 합니다.

-- 코드를 입력하세요
SELECT hour(datetime) as hour, count(datetime) as count from ANIMAL_OUTS 
group by hour having hour >= 9 and hour <=19
order by hour

• 입양 시각 구하기(2)

보호소에서는 몇 시에 입양이 가장 활발하게 일어나는지 알아보려 합니다. 0시부터 23시까지, 각 시간대별로 입양이 몇 건이나 발생했는지 조회하는 SQL문을 작성해주세요. 이때 결과는 시간대 순으로 정렬해야 합니다.

set @hour := -1;
SELECT 
    (@hour := @hour + 1) as hour,
    (select count(*) from animal_outs where hour(datetime) = @hour) as count
from 
    animal_outs
where
    @hour < 23;

MySQL에서 '='연산자는 두 가지 의미로 해석된다.

• SET문이나 UPDATE문의 SET 절에서 사용되면, 대입연산자로 해석된다.
• 그러나 그 이외에서 사용되면, 비교 연산자로 해석된다.

이처럼 '=' 연산자는 상황에 따라 다르게 해석될 수 있으므로, 작성자의 의도와 다르게 해석될 여지가 있다.

따라서 MySQL에서는 언제나 대입 연산자로만 해석되는 ':=' 대입연산자를 별도로 제공하고 있다. 

문제링크:https://www.acmicpc.net/problem/10825

그리디 알고리즘입니다. (사실 그리디라고도 할 수 없는 단순 정렬문제)

algorithm 라이브러리에 sort함수를 구현해 해결했습니다.

cmp는 오버라이딩 된 형태라 직접 구현할 수 있습니다. 

주석에 써놓은 번호순서대로 문제에서 요구하는 정렬을 구현한 것입니다. 

bool cmp(info a, info b) {
	if (a.korean > b.korean)  //1
		return true;
	else if(a.korean == b.korean){
		if (a.english < b.english) return true; //2
		else if(a.english == b.english){
			if (a.math > b.math) return true; //3
			else if(a.math == b.math) {
				if (a.name < b.name)return true; //4
			}
		}
	}

	return false;
}

처음에 시간초과가 났습니다. n = 100000 이고 sort 함수를 O(nlgn) 이기때문에 정렬의 문제는 아니였습니다. 

endl << 이 너무 많은 시간을 잡아먹어서 에러가 났었습니다. endl는 버퍼를 flush하는 역할을 겸하기 때문에 위 처럼 많은 출력을 해야해서 endl이 많이 사용될때는 endl사용을 지양하고 '\n'을 사용해야 합니다.

정답코드입니다.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct info {
	string name;
	int korean;
	int english;
	int math;
};

info arr[100001];
int n = 0;

/*
국어 점수가 감소하는 순서로
국어 점수가 같으면 영어 점수가 증가하는 순서로
국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)
*/
bool cmp(info a, info b) {
	if (a.korean > b.korean)  //1
		return true;
	else if(a.korean == b.korean){
		if (a.english < b.english) return true; //2
		else if(a.english == b.english){
			if (a.math > b.math) return true; //3
			else if(a.math == b.math) {
				if (a.name < b.name)return true; //4
			}
		}
	}

	return false;
}
int main() {

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i].name >> arr[i].korean >> arr[i].english >> arr[i].math;

	sort(arr, arr + n, cmp);

	for (int i = 0; i < n; i++)
		cout << arr[i].name <<'\n';

}

꼭 직접 작성해보시기 바랍니다:) 화이팅

문제링크:https://www.acmicpc.net/problem/14570

간만에 털렸습니다...

우선 시뮬레이션 문제로 인식했습니다. 문제에서 요구하는 조건 그대로 이동하면서 결과값을 도출하게 끔 구현을 했습니다.

문제조건인 

1. 현재 구슬이 놓인 노드의 자식이 없다면 그 자리에서 멈춘다.
2. 1을 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 한 개라면 해당 자식 노드로 떨어진다.
3. 1, 2를 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 두 개라면,
   1. 현재 노드의 왼쪽 서브트리에 담긴 모든 구슬의 수 <= 오른쪽 서브트리에 담긴 모든 구슬의 수일 경우, 왼쪽 자식 노드로 떨어진다.
   2. 그 외의 경우에는 오른쪽 자식 노드로 떨어진다.
4. 1~3번의 조건을 다시 체크하고 되풀이한다.

를 생각하면서 구현한 답입니다.

#include <iostream>
using namespace std;

int n, u, v;
long long k;
int result = 0;
struct node {
	int left = 0;
	int right = 0;
};
node arr[200001];
int cnt[200001] = { 0 };
int left_cnt, right_cnt;

void add_cnt(int current,int direction) {
	
	if (arr[current].left == 0 && arr[current].left == 0) {
		if (direction == 0)
			left_cnt += cnt[current];
		else
			right_cnt += cnt[current];

		return;
	}
	if (arr[current].left != 0)  add_cnt(arr[current].left,direction);
	if (arr[current].right != 0)   add_cnt(arr[current].right, direction);

}

void action(int current,int i) {

	//1
	if (arr[current].left == 0 && arr[current].left == 0) {
		cnt[current]++;

		result = current;
		return;
	}
	//2
	else if ((arr[current].left != 0 && arr[current].right == 0)) action(arr[current].left,i);
	else if ((arr[current].left == 0 && arr[current].right != 0)) action(arr[current].right,i);
	//3
	else if (arr[current].left != 0 && arr[current].left != 0) {
		/*
		left_cnt = 0, right_cnt = 0;
		add_cnt(arr[current].left,0);
		add_cnt(arr[current].right,1);
		if(left_cnt <= right_cnt) action(arr[current].left);
		else action(arr[current].right);	
		*/

		if(i%2) action(arr[current].left,i/2 +1);
		else action(arr[current].right, i/2);
	}
}

int main() {

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> u >> v;
		if (u != -1 || v != -1) {
			arr[i].left = u;
			arr[i].right = v;
		}
	}

	cin >> k;

	for (int i = 1; i <= k; i++)
		action(1,i); //루트는 항상 1번 노드이다.

	cout << result << endl;
	
}

이러한 방식입니다. 문제가 많은 코드입니다. 

왜냐하면 1 ≤ K ≤ 10^18, 1 ≤ N ≤ 200000  이기 때문에 저렇게 무식한 시뮬레이션으로는 문제를 시간초과가 납니다.

규칙을 찾아야합니다. 

위와 같은 문제 규칙에서 2번, 4번, 2번, 5번, 2번 노드에 차례대로 떨어지게 됩니다. 

루트노드입장에서 생각해봅시다. k번째를 반복하며 인덱스가 홀수에서는 왼쪽 짝수에서는 오른쪽으로 이동합니다.

3의 입장에서도 보면 인덱스가 홀수에서는 왼쪽 짝수에서는 오른쪽으로 이동합니다. 

이러한 규칙이 있기 때문에 굳이 시뮬레이션할 필요가 없습니다.

즉 k번을 반복하는게 아니라, k번째만 확인해 답을 구할 수 있습니다.

정답코드입니다.

#include <iostream>
using namespace std;
struct node {
	int left, right;
};

node arr[200001];

int main() {
	int n; long long k;

	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i].left >> arr[i].right;

	cin >> k;

	int pos = 1; //루트 노드에서 시작
	while (1) {
		//1
		if (arr[pos].left == -1 && arr[pos].right == -1) break;
		//2
		else if (arr[pos].left == -1) pos = arr[pos].right; //왼쪽노드가 없음 -> 오른쪽으로 이동
		else if (arr[pos].right == -1) pos = arr[pos].left; //오른쪽노드가 없음 -> 왼쪽으로 이동
															//3
		else if (k % 2) {//1)조건 -> 홀수면 왼쪽으로 간다.
			pos = arr[pos].left, k = k / 2 + 1;
		}
		else { //2)조건 -> 짝수면 오른쪽으로 간다.
			pos = arr[pos].right, k /= 2;
		}
	}
	cout << pos << endl;

	return 0;
}

이중에서  아래 코드를 봅시다.

while (1) {
		//1
		if (arr[pos].left == -1 && arr[pos].right == -1) break;
		//2
		else if (arr[pos].left == -1) pos = arr[pos].right; //왼쪽노드가 없음 -> 오른쪽으로 이동
		else if (arr[pos].right == -1) pos = arr[pos].left; //오른쪽노드가 없음 -> 왼쪽으로 이동
															//3
		else if (k % 2) {//1)조건 -> 홀수면 왼쪽으로 간다.
			pos = arr[pos].left, k = k / 2 + 1;
		}
		else { //2)조건 -> 짝수면 오른쪽으로 간다.
			pos = arr[pos].right, k /= 2;
		}
	}

1,2번 조건은 쉽게 이해하실겁니다. 아래 코드에서 k%2와 k/2를 통해서 위치를 판별합니다. 

루트기준으로 k번째에서의 떨어지는 방향은 홀수면 왼쪽으로 짝수면 오른쪽으로 이동합니다. 

그아래 노드들도 위에서 설명한 규칙대로 이동하기 때문에 k값의 짝,홀수 를 변경해주는 것 입니다. 

문제링크:https://www.acmicpc.net/problem/9205

문제접근을 하는데 어려움을 겪었습니다.

처음에 가진 생각은 가장 이동경로내에 여러개의 편의점이 있으면 어디를 선택할까와 같은 생각을 했지만, 다시 생각해보니 무의미했습니다. yes, no로 도달할 수 있는지만 판단하면 되었기 때문입니다. 그렇기 때문에 모든 편의점을 탐색하며 도달할 수 있는지 여부만 판단했습니다.

bfs알고리즘을 사용해서 방문여부를 판단했습니다.

주의 하셔야 할 점은  두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리) 입니다.

문제를 꼼꼼히 읽는 습관을 가져야 합니다.

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;
int t = 0, n = 0;
int arr[101][2] = { 0 };
int starting_x, starting_y, destination_x, destination_y;
bool visited[101];
int que[1000000][2] = { 0 };
int started = 0, ended = 0;

void bfs() {
	que[ended][0] = starting_y;
	que[ended++][1] = starting_x;

	while (started != ended) {
		int y = que[started][0];
		int x = que[started++][1];

		for (int i = 0; i <= n; i++) {
			if (!visited[i]) {
				int len_x = min(abs(x - arr[i][1]), abs(arr[i][1] - x));
				int len_y = min(abs(y - arr[i][0]), abs(arr[i][0] - y));
				double len_total = len_x + len_y;
				if (len_total <= 1000)
				{
					visited[i] = 1;
					que[ended][0] = arr[i][0];
					que[ended++][1] = arr[i][1];
				}
				
			}
		}
	}

}
int main() {
	cin >> t;

	while (t--) {
		cin >> n;
		cin >> starting_x >> starting_y;
		for (int i = 0; i < n; i++)
			cin >> arr[i][1] >> arr[i][0];
		cin >> arr[n][1] >> arr[n][0];

		memset(visited, 0, sizeof(visited));
		started = 0, ended = 0;

		bfs();
		if (visited[n])
			cout << "happy" << endl;
		else
			cout << "sad" << endl;
	}


}