#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int N, M;
int A, B;
bool visited[101];
vector<int> vec[101];
int cnt = 0;
void BFS(int start, int end) {
queue<pair<int, int>> q;
q.push({ start, 0 });
visited[start] = true;
while (!q.empty()) {
int cur = q.front().first;
int num = q.front().second;
q.pop();
if (cur == end) {
cnt = num;
break;
}
for (int i{ 0 }; i < vec[cur].size(); i++) {
if (!visited[vec[cur][i]]) {
q.push({ vec[cur][i], num + 1 });
visited[vec[cur][i]] = true;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (int i{ 0 }; i < M; i++) {
cin >> A >> B;
vec[A].push_back(B);
vec[B].push_back(A);
}
int min = 98765432;
int ans = 0;
for (int i{ 1 }; i <= N; i++) {
int temp = 0;
for (int j{ 1 }; j <= N; j++) {
memset(visited, false, sizeof(visited));
if (i != j) {
BFS(i, j);
temp += cnt;
cnt = 0;
}
}
if (min > temp) {
min = temp;
ans = i;
}
}
cout << ans;
}
- 각 지역의 높이를 입력 받으면서 가장 높은 지역의 값을 maxHeight 변수에 저장해 놓는다. (가장 높은 지역의 높이보다 큰 비가 내리면 어차피 다 잠기기 때문에 똑같기 때문에 maxHeight까지만 반복하면 됨)
- x = 0 (*이때, x = 1부터 돌게 되면 틀린다!!이거 때문에 계속 틀림)부터 앞에서 구한 maxHeight 까지 반복하면서 BFS를 돌린다. 이때 당연히 아직 방문하지 않았고, 안전한 구역인 곳만 BFS를 실행한다. (안전한 구역 => 현재 x 값보다 큰 구역)
*x = 0로 돌릴 때 틀리는 이유는 문제에 나와있는 이 조건 때문인 듯하다.
📍 코드
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int N;
int arr[101][101];
bool visited[101][101];
int xDir[4] = { 1,-1,0,0 };
int yDir[4] = { 0,0,1,-1 };
void BFS(int i,int j, int bound) {
queue<pair<int, int>> q;
q.push({ i,j });
visited[i][j] = true;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i{ 0 }; i < 4; i++) {
int nowX = x + xDir[i];
int nowY = y + yDir[i];
if (nowX < 0 || nowY < 0 || nowX >= N || nowY >= N) {
continue;
}
if (visited[nowX][nowY]) {
continue;
}
// 물에 잠긴 경우 (bound이하)
if (arr[nowX][nowY] <= bound) {
continue;
}
q.push({ nowX,nowY });
visited[nowX][nowY] = true;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
int maxHeight = -1;
int max = 0;
for (int i{ 0 }; i < N; i++) {
for (int j{ 0 }; j < N; j++) {
cin >> arr[i][j];
if (maxHeight < arr[i][j]) {
maxHeight = arr[i][j];
}
}
}
for (int x{ 0 }; x <= maxHeight; x++) {
memset(visited, false, sizeof(visited));
int ans = 0;
for (int i{ 0 }; i < N; i++) {
for (int j{ 0 }; j < N; j++) {
// 방문하지 않았고 안전한 구역
if (!visited[i][j] && arr[i][j] > x) {
BFS(i, j, x);
ans++;
}
}
}
if (max < ans) {
max = ans;
}
}
cout << max;
}
#include<iostream>
#include<queue>
using namespace std;
int N, M; // 행, 열
char arr[100][100];
int xDir[4] = { 1,-1,0,0 };
int yDir[4] = { 0,0,1,-1 };
bool visited[100][100];
int dist[100][100]; // 지나야 하는 칸 수 저장하는 배열
queue<pair<int, int>> q;
int BFS() {
dist[0][0] = 1;
visited[0][0] = true;
q.push({ 0,0 });
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i{ 0 }; i < 4; i++) {
int nowX = x + xDir[i];
int nowY = y + yDir[i];
if (nowX < 0 || nowX >= N || nowY < 0 || nowY >= M) {
continue;
}
if (arr[nowX][nowY] == '0') {
continue;
}
if (visited[nowX][nowY]) {
continue;
}
visited[nowX][nowY] = true;
q.push({ nowX,nowY });
dist[nowX][nowY] = dist[x][y] + 1;
}
}
return dist[N - 1][M - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (int i{ 0 }; i < N; i++) {
for (int j{ 0 }; j < M; j++) {
cin >> arr[i][j];
}
}
cout << BFS();
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N = 0; // 지방의 수
int money = 0; // 배정된 예산
int max = 0; // 총 예산
int answer = 0; // 답
cin >> N;
vector<int> v;
// 각 지방의 예산요청 입력 받기
for (int i{ 0 }; i < N; i++) {
cin >> money;
v.push_back(money);
}
cin >> max;
sort(v.begin(), v.end());
int start = 1;
int end = v.back();
while (start <= end) {
int mid = (start + end) / 2;
int sum = 0;
for (int i{ 0 }; i < v.size(); i++ ) {
if (v[i] <= mid) {
sum += v[i];
}
else {
sum += mid;
}
}
// 예산을 초과하는 경우
if (sum > max) {
end = mid - 1;
}
// 예산을 초과하지 않는 경우
else {
if (mid <= end) {
answer = mid;
}
start = mid + 1;
}
}
cout << answer;
}
먼저 입력 받은 numbers 들을 string으로 변환하여 vector에 삽입한다.그리고 나서 정렬을 할 건데, (여기서 sort와 사용자 정의 compare 함수를 사용하였다.)
compare 함수에서는for문을 돌며
a[i]와 b[i]가 같다면 a+b를 int로 바꾼 것과 b+a를 int로 바꾼 것 중 더 큰 수를 가지는 문자열을 결정한다.(예를 들어 "3" 과 "30"을 비교할 때, 0번째 인덱스에서 두 문자열이 동일한 숫자를 가지고 있다. 따라서 stoi("3"+"30") 와 stoi("30"+"3") 를 비교하면 330이 303보다 크다. )
그렇지 않다면,(a[i]와 b[i]가 같지 않다면)
a[i]와 b[i]를 비교하여 더 큰 숫자를 가진 문자열을 결정한다.
그런데, 이렇게 코드를 쓰고 제출하면 테스트케이스 11에서만 실패가 뜬다.
🖐 여기서 잠깐!
이 문제에는 예외 처리 해야 하는 케이스가 하나 있다.
모든 numbers가 0일 때 ( [0, 0, 0, 0] 의 경우, "0000"으로 출력됨)
따라서, answer의 첫 원소가 "0"인 경우, "0"을 return하는 예외 처리를 해 주어야 한다.
📍 코드
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(string a, string b) {
bool answer = true;
int mx = max(a.size(), b.size());
for (int i{ 0 }; i < mx; i++) {
if (int(a[i]) == int(b[i])) {
answer = stoi(a + b) > stoi(b + a);
break;
}
else {
answer = a[i] > b[i];
break;
}
}
return answer;
}
string solution(vector<int> numbers) {
string answer = "";
vector<string> v;
for (int i{ 0 }; i < numbers.size(); i++) {
v.push_back(to_string(numbers[i]));
}
sort(v.begin(), v.end(),compare);
if (v[0] == "0") {
return "0";
}
for (int i{ 0 }; i < v.size(); i++) {
answer += v[i];
}
return answer;
}
