문제풀이
이 문제는 개수만 세면 되기 때문에 실제 움직임을 구현해야 하는 지 중요함. 결과적으로 실제 움직임을 구현할 필요는 없음. N과 S극이 한 쌍씩 연결이 되는 지가 중요한데, 즉 하나의 열을 관찰할 때, N이 나오고 그 다음 S가 나오면 교착 상태의 개수가 하나 증가함.
하나의 쌍을 엮기 위해서 벡터 자료형을 사용하였는 데, 예를 들어 S가 나왔을 때 벡터의 마지막 원소가 N이었을 경우 N-S 하나로 엮게 됨. 결과적으로 이 구조가 만족되어야만 교착이 일어나기 때문임.
벡터 v를 가정하였을 때, 벡터 원소를 초기화하는 v.clear();와 마지막 원소를 가리키는 v.back();을 사용하였음. 벡터의 처음과 마지막 원소값이 필요할 때 각각 v.front();와 v.back();을 사용하면 됨. iterator인 v.begin();과 v.end();와 혼동ㄴㄴ
소스코드
#include <iostream>
#include <vector>
#define MAX 100
using namespace std;
int map[MAX][MAX];
int up=-1;
int down=1;
int N=1;
int S=2;
int cnt;
vector <int> v;
void input()
{
for (int i=0; i<MAX; i++)
{
for (int j=0; j<MAX; j++)
{
cin>>map[i][j];
}
}
}
void count()
{
for (int j=0; j<MAX; j++)
{
v.clear();
for (int i=0; i<MAX; i++)
{
if (map[i][j]==N)
{
v.push_back(N);
}
else if ((v.back()==N) && (map[i][j]==S))
{
v.clear();
cnt++;
}
}
}
}
void print()
{
for (int i=0; i<MAX; i++)
{
for (int j=0; j<MAX; j++)
{
cout<<map[i][j];
}
cout<<endl;
}
}
int main()
{
int test;
freopen("input.txt", "rt", stdin);
for (int i=0; i<10; i++)
{
cnt=0;
cin>>test;
input();
count();
// print();
cout<<"#"<<i+1<<" "<<cnt<<endl;
}
return 0;
}
'C C++ > C C++ 알고리즘 문제 기타' 카테고리의 다른 글
[C/C++] 석차 구하기 (0) | 2022.09.28 |
---|---|
[C/C++] 유쾌한 점퍼 (Jolly Jumper) (0) | 2022.09.27 |
[C/C++] swea 1209. [S/W 문제해결 기본] 2일차 - Sum (1) | 2022.09.24 |
[C/C++] swea 2805. 농작물 수확하기 (1) | 2022.09.21 |
[C/C++] 백준 1547번 공 (0) | 2022.09.17 |
댓글