문제

대략 해석해보자면 전국 프로그래밍 대회가 열리는데 그 전에 지역마다 예선을 치뤄서 각 지역마다 대표 2명을 뽑아서 참가하게 하려는데 대표 2명을 구성할수 있는 경우가 유니크(단 한 가지)한지 판별해야 하는 문제이다.

입력은 첫 줄에 전체 학생 수 N과 전체 지역 수 M이 들어오고 2번째 줄부터 N+1번째 줄까지 이름, 지역 번호, 점수(0~800)가 들어온다.

우리는 그 데이터를 가지고 각 지역의 대표를 구성할수 있는 경우가 유니크한지, 유니크 하다면 점수->이름(Sort by score, then by name)순으로 정렬된 대표들을 출력하는 것이다. 만약에 유니크하지 않는다면 ?를 출력하면 된다.

풀이

배열에 이름과 점수를 모두 가지고 정렬을 해야하므로 map을 사용할까 set을 사용할까 생각하다가 그냥 vector<pair<string,int>>를 사용하기로 결정하고 해당 vector를 배열로 만들어 vector[지역번호] 식으로 사용하였다.

학생의 이름, 지역 번호, 점수를 받은 뒤 vector[지역 번호].push_back(make_pair(이름, 점수)) 식으로 데이터를 넣었고 정렬은 <algorithm>에 있는 stable_sort를 이용하여 직접 점수 정렬 후 이름 정렬을 구현 하였다.

또한 각 팀마다 같은 점수가 몇 명 있는지 확인하기 위해 hi라는 배열을 만들어 기저 사례를 처리하였다.

기저 사례

1. 가장 높은 점수가 2명이면 바로 해당 학생들의 이름을 출력

2. 가장 높은 점수가 3명 이상 있거나 한 지역의 참가 학생이 2명보다 적으면 ?를 출력

또한 가장 높은 점수가 1명이더라도 두번째로 높은 점수가 여러명이면 유니크한 경우가 아니므로 확인 후 ?를 출력하게 하였다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define INT_MAX 987654321
using namespace std;

bool cmp(const pair<string,int>& val1, const pair<string,int>& val2){
	if(val1.second!=val2.second)
		return val1.second>val2.second;
	else
		return val1.first<val2.first;
}

int main()
{
	int n,m,i,j,**hi;
	vector<pair<string,int>> *v;

	cin.sync_with_stdio(false);
	cin>>n>>m;
	v = new vector<pair<string,int>>[m+1];
	hi = new int*[m+1];

	for(i=1;i<=m;i++){
		hi[i] = new int[801]();
	}

	for(i=0;i<n;i++){
		string name;
		int team,score;

		cin>>name>>team>>score;

		v[team].push_back(make_pair(name,score));
		hi[team][score]++;
	}

	for(i=1;i<=m;i++){
		stable_sort(v[i].begin(),v[i].end(),cmp);

		if(hi[i][v[i][0].second]>2 || v[i].size() < 2) {
			cout << "?\n";
		}
		else {      
			if(hi[i][v[i][0].second] == 2)
			{
				cout << v[i][0].first << " " << v[i][1].first << "\n";
				continue;
			}

			int secondary = INT_MAX;

			for(j=0;j<v[i].size();j++){
				if(v[i][0].second != v[i][j].second){
					secondary = v[i][j].second;
					break;
				}
			}

			if(secondary != INT_MAX && hi[i][secondary]>1)
				cout << "?\n";
			else
				cout << v[i][0].first << " " << v[i][1].first << "\n";
		}
	}
}

문제

간단한 BFS를 이용한 길 찾기 문제이다. 알고리즘 분류는 BFS로 되어있는데 당연히 DFS로도 된다. 나는 BFS로 구현했다.

소스

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

struct pt{
	int x;
	int y;
};

int map[501][101] = {0};
int visit[501][101] = {0};
queue<pt> q;

void setVisit(int x, int y, pt o){
	pt next;
	next.x = x;
	next.y = y;
	q.push(next);
	visit[y][x]+=visit[o.y][o.x]+1;
}
int main(){
	
	int n,m,i,j;char c;
	pt o;
	cin>>n>>m;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++) {
			cin >> c;
			map[i][j]=c-'0';
		}
	}
	o.x=0;o.y=0;
	q.push(o);
	visit[0][0]=1;
	while(!q.empty()){
		pt front = q.front();
		q.pop();
		if(front.x-1 >= 0 && !visit[front.y][front.x-1] && map[front.y][front.x-1])
			setVisit(front.x-1,front.y,front);
		if(front.x+1 < m && !visit[front.y][front.x+1] && map[front.y][front.x+1])
			setVisit(front.x+1,front.y,front);
		if(front.y-1 >= 0 && !visit[front.y-1][front.x] && map[front.y-1][front.x])
			setVisit(front.x,front.y-1,front);
		if(front.y+1 < n && !visit[front.y+1][front.x] && map[front.y+1][front.x])
			setVisit(front.x,front.y+1,front);
	}
	cout << visit[n-1][m-1] << '\n';
}

각 줄마다 띄어쓰기 없이 미로가 주어지므로 char 형으로 받은 다음 '0'(48)을 빼주어 정수형으로 바꾸어주었다.

큐에는 이번에 탐색해야할 좌표 값을 저장해야하므로 x,y값을 가지는 구조체를 만들어 좌표값을 저장시켜 주었고 맨 처음 시작할때 0,0 좌표 변수를 만들어 큐에 넣어주고 시작하게 했다.

탐색을 할때 상하좌우에 이동 할 수 있으며 방문하지 않은곳이 있다면 방문을 했다는 표시를 하고(어차피 큐에 넣고 나중에 방문할것이니 미리 표시해도 상관이 없다) visit[y][x]변수에 몇 번 이도해서 x,y 좌표에 왔는지에 대한 횟수를 적어두게하였다.