코딩무식자 전공생

문제출처: https://www.acmicpc.net/problem/1012

BFS를 이용한 풀이입니다. DFS를이용한 풀이는 링크를 참조해주세요. https://jow1025.tistory.com/88

풀이

배추흰지렁이의 최소 수는 문제에도 힌트가 있는데, 배추가 있는 부분의 영역의 갯수입니다. 말로하면 헷갈릴 수 있으니 아래 그림을 참고해주세요.

즉, 배추흰지렁이의 최소 수는 bfs or dfs연산의 횟수(조건에 맞게 돌렸을 때), 즉 배추의 요소의 갯수라고 할 수 있습니다. 좌표가 헷갈릴 수 있으니 그것만 주의하시면 되고, 다른것은 어렵지않으므로 설명은 소스코드로 대체하겠습니다.

코드

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int map[50][50];
int check[50][50];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int m, n, k;
//가로, 세로,배추위치갯수
void bfs(int y,int x);
int main()
{
	int t;
	cin >> t;
	int x, y;
	while (t--)
	{
		memset(map, 0, sizeof(map));
		memset(check, 0, sizeof(check));
		cin >> m >> n >> k;
		int ans = 0;
		for (int i = 0; i < k; i++)
		{
			//좌표조심
			cin >> x >> y;
			map[y][x] = 1;
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (map[i][j] == 1 && check[i][j] == 0)
				{
					bfs(i, j);
					ans++;
				}
			}
		}
		cout << ans << endl;
	}
}
void bfs(int y, int x)
{
	check[y][x] = 1;
	queue<pair<int, int>>q;
	q.push(make_pair(y, x));
	while (!q.empty())
	{
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && nx >= 0 && nx < m && ny < n) {
				if (map[ny][nx] == 1 && check[ny][nx] == 0)
				{
					q.push({ ny,nx });
					check[ny][nx] = 1;
				}
			}
		}
	}
	
}

결과

문제출처: https://www.acmicpc.net/problem/2178

풀이

최단거리구하기. 즉 dfs가 아닌 bfs를 사용해야합니다.  저는 방문 배열을 선언하여 0을 방문하지않았을 때를 의미하고 그외에 모든 양수값은 방문처리가 되었을때, 그리고 동시에 그값이 최단거리(칸)을 의미하게 함으로써 check[n-1][m-1]이 답이 될 수 있게끔 로직을 구성했습니다. 

1. map을 입력받습니다.

2. 0,0좌표를 시작으로 bfs를 돌립니다. 주위에 길이있고 방문하지않은 좌표를 최단칸으로 갱신합니다.(check배열로 갱신)

3. 최종적으로 check[n-1][m-1]은 0,0좌표부터 현재의 좌표까지의(답) 최단칸수입니다.

코드

#include<iostream>
#include<queue>
using namespace std;
char map[100][100];
int check[100][100];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int n, m;
void bfs(int y, int x);
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> map[i];
	//시작위치가 정해져있으므로 바로 bfs!
	bfs(0, 0);
	//15행 선언후 아래 행 먼저선언하자(어짜피 머릿속으로 이렇게 계산하자고생각했으므로)
	//check배열에 0,0부터 현재좌표까지의 최단칸수담음
	cout << check[n - 1][m - 1] << endl;
}
void bfs(int y,int x)
{
	queue<pair<int, int>>q;
	q.push({ y,x });
	check[y][x] = 1;
	while (!q.empty())
	{
		x=q.front().second;
		y=q.front().first;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				//길이있고, 방문하지않았으면 방문 및 최단거리 갱신
				if (map[ny][nx] == '1' && check[ny][nx] == 0)
				{
					q.push({ ny,nx });
					check[ny][nx] = check[y][x] + 1;
				}
			}
		}
	}
}

결과

문제출처: https://www.acmicpc.net/problem/7576

풀이

길게 늘여놓으면 이해가 안될 것같아 순서대로 풀이를 적겠습니다.

1. 입력받을 map, 좌표, 큐를 선언합니다.

2. 입력받으면서 익은토마토의 좌표를 큐에 넣습니다.

3. bfs함수를 돌립니다.

4. bfs함수에서, 익은 토마토좌표 주위의 안익은 토마토좌표의값을 익은 토마토좌표에 저장된값으로부터 +1해줍니다.

(bfs에서 익은 토마토좌표를이용해 연산하므로 1번에서 언급한 큐를 전역으로 선언한 이유입니다.)

5. 안익은토마토의 좌표를 +1해주는 이유는 0이아니게해주고(익게해주고), 궁극적으로는 답인 최소날짜를 구하기위함입니다. 익은게 1로 표현되므로 날짜를 구하기 좋은 조건입니다. 이 때, ans(날짜)를 0으로 선언하면 예제입력5를 입력하면 -1이 됨으로 1로 선언해둡니다.(예제코드를 입력해보다가 오류가 나서 발견했습니다.)

6. 주위 토마토를 익게하는 연산을 할 때 마다 ans(날짜)를 더 큰값으로 초기화해줍니다.

7. bfs연산을 마치고 map을 확인합니다. 좌표값이 0인 좌표가 존재하면 익을 수 없으므로 -1출력 뒤 종료합니다. 그리고 5번에서 설명했듯이 map의 좌표는 최소 일수들로 갱신된상태입니다. 그런데 연산최초에 익은 토마토주위의 값은 2인데, 2일이 지난게 아니라 1일이 지난것이므로 출력할 때 -1해줍니다.

주의할 것은 ans를 0이 아닌 1로 선언해야한다는 것입니다. 

(예제입력을 발견하다가 수정했더니 정답이네요,, 이부분에서 명확하게 1로선언해야하는 이유나 이렇게 애매한 선언을 방지하기위한 장치나, 다른 방법의연산방법이 있다면 알려주세요!!)

코드

#include<iostream>
#include<queue>
using namespace std;
int map[1000][1000];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int m, n;
queue<pair<int, int>>q;
//ans를 0으로 해두면 예제입력5 설명불가
int ans = 1;
void bfs();
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> m >> n;
	//토마토있는 좌표만 큐에넣음
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 1)
			{
				q.push({ i,j });
			}
		}
	}
	bfs();
	//bfs를 돌리고나면 map은 토마토가익는 날(+1)로초기화됨
	//토마토있을때1이므로 그주변이 익을 때 1일이아닌 2일로표현되므로
	//답을 출력할때 -1해줘야함.
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			//0이있으면 익지못한곳이있으므로 -1출력
			if (map[i][j] == 0)
			{
				cout << -1 << '\n';
				return 0;
			}
		}
	}
	//30~32행에서 언급했듯이 -1해줘야함. 
	cout << ans - 1 << '\n';
}
void bfs()
{
	while (!q.empty())
	{
		int x = q.front().second;
		int y = q.front().first;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				if (map[ny][nx] == 0)
				{
					//익은곳주위의 토마토가안익은곳을 +1해줌
					//+1해주는 이유는 최소날짜를 구하기위함
					map[ny][nx] = map[y][x] + 1;
					q.push({ ny,nx });
					//초기화시켜줌.
					if (ans < map[ny][nx])
					{
						ans = map[ny][nx];
					}
				}
			}
		}
	}
}

결과

문제출처: https://www.acmicpc.net/problem/1668

풀이

간단한 탐색 문제입니다. 왼쪽에서볼때, 오른쪽에서 볼때의 각각 보이는 높이를 구하면됩니다. 각 경우별로 트로피높이를 비교할 때 제일 높은 트로피로 갱신해주며 계산하면됩니다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int trophy[50];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> trophy[i];
	
	int left = 0;
	int right = 0;
	int left_max = -1;
	int right_max = -1;
	
	for (int i = 0; i < n; i++)
	{
		if (left_max < trophy[i])
		{
			left_max = trophy[i];
			left++;
		}
		if (right_max < trophy[n - 1 - i])
		{
			right_max = trophy[n - i - 1];
			right++;
		}
	}
	cout << left << endl << right << endl;
	

}

결과

문제출처: https://www.acmicpc.net/problem/1543

풀이

정답률이 예상외로 낮네요.. 아마도 c언어로 구현하는데 문자열을 입력할 때 공백까지 포함해서 입력받는법을 모르셨거나, c++로 구현시 공백을 감안하지않은 분들이 많았기 때문일겁니다. 저는 c++ string 으로 구현하였는데, 문자열입력시 getline함수만 사용하면 쉽게 풀리는 것 같습니다!

코드

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s1, s2;
	getline(cin, s1);
	getline(cin, s2);
	int cnt = 0;
	if (s1.size() < s2.size())
	{
		cout << 0 << endl;
		return 0;
	}
	for (int i = 0; i <= s1.size()-s2.size();)
	{
		bool check = true;
		for (int j = 0; j < s2.size(); j++)
		{
			if (s1[i + j] != s2[j])
			{
				check = false;
				break;
			}
		}
		if (check)
		{
			cnt++;
			i += s2.size();
		}
		else
			i++;
	}
	cout << cnt << endl;
}

결과

문제출처: https://www.acmicpc.net/problem/1296

풀이

간단한 문자열문제입니다. c언어스타일로 오민식이름에서 L,O,V,E의 갯수 + 입력받는 여자의 이름의 L,O,V,E의 갯수를 합하여 계산값이 가장 크면서 사전순으로 앞에있는 여자의 이름을 출력하면 됩니다. 저는 string으로 풀었습니다.  string으로 풀 때는 모두 입력받고 정렬 시킨뒤 계산하는게 편합니다.

코드

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;
int max_value = -1;
string arr[50];
int main()
{
	int n;
	//L,O,V,E
	string a;
	cin >> a >> n;
	int index = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + n);
	for(int i=0;i<n;i++)
	{
		string temp = "";
		int l=0, o=0, v=0, e=0;
		temp = a + arr[i];
		for (int i = 0; i < temp.size(); i++)
		{
			if (temp[i] == 'L')
				l++;
			else if (temp[i] == 'O')
				o++;
			else if (temp[i] == 'V')
				v++;
			else if (temp[i] == 'E')
				e++;
		}
		if (max_value < ((l + o) * (l + v) * (l + e) * (o + v) * (o + e) * (v + e)) % 100)
		{
			max_value = ((l + o) * (l + v) * (l + e) * (o + v) * (o + e) * (v + e))%100;
			index = i;
		}
	}
	cout << arr[index]<<endl;
}

결과

문제출처: https://www.acmicpc.net/problem/1448

풀이

https://jow1025.tistory.com/35에도 나와있듯이, 삼각형의 성립조건은 세 변 a,b,c중 c가 가장 큰 변일 때 a+b>c일때입니다.

a+b>c일때 a,b,c의 합의 최댓값은 빨대의길이를 정렬하고 뒤에서부터(큰값부터)비교하면 됩니다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int straw[1000001];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> straw[i];
	sort(straw + 1, straw + n + 1);
	//c가 가장 큰 변일 떄 a+b>c일떄 삼각형성립
	for (int i = n; i >= 2; i--)
	{
		int c = straw[i];
		int a = straw[i - 1];
		int b = straw[i - 2];
		if (a + b > c)
		{
			cout << a + b + c << '\n';
			return 0;
		}
	}
	cout << -1 << '\n';
}

결과

문제출처: https://www.acmicpc.net/problem/18258

문제

이 문제는 여러분이 사용하는 큐 자료구조가 시간 복잡도 상으로 충분히 빠른지 테스트하는 문제이다. 입력의 범위를 제외하면 10845 (큐) 문제와 같다.

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

#include<iostream>
#include<queue>
#include<cstring>
char word[10];
using namespace std;
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n; cin >> n;
	 int x;
	queue<int>q;
	for (int i = 0; i < n; i++)
	{
		cin >> word;
		if (!strcmp(word, "push"))
		{
			cin >> x;
			q.push(x);
		}
		else if (!strcmp(word, "pop"))
		{
			if (q.size() == 0)
				cout << -1 << '\n';
			else {
				cout << q.front() << '\n';
				q.pop();
			}
		}
		else if (!strcmp(word, "front"))
		{
			if (q.size() == 0)
				cout << -1 << '\n';
			else

			cout << q.front() << '\n';
		}
		else if (!strcmp(word, "back"))
		{
			if (q.size() == 0)
				cout << -1 << '\n';
			else

			cout << q.back() << '\n';
		}
		else if (!strcmp(word, "size"))
		{
			cout << q.size() << '\n';
		}
		else if (!strcmp(word, "empty"))
		{
			cout << q.empty() << '\n';
		}
	}
}