작은시작

https://programmers.co.kr/learn/courses/30/lessons/42628

코드 설명

기존에는 문제처럼 priority_queue 두개를 할당해서 구현하다가 문제를 깨달았다. 큐를 두개 할당하고 문제를 풀때 최댓값을 지우고 최솟값을 지우는 과정에서 없어져야 할 숫자가 계속 남는 문제가 생긴다

(이를 해결하려면 cnt변수를 할당해서 넣고 빼는 횟수가 같다면 큐를 전부 비워주어야한다)

그래서 저는 아예 vector 하나에 할당하여 매번 sort시켜주고 앞,뒤에서 각각 빼주는 방식을 생각하였습니다. (시간복잡도는 더 늘어날듯..)

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
  vector<int> result;
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    for(int i=0;i<operations.size();i++){
        bool I_flag=false;
        bool D_flag=false;
        string abc="";
        for(int j=0;j<operations[i].size();j++){
            
            if(operations[i][j]=='I'){
                I_flag=true;
                
            }
            else if(operations[i][j] == 'D'){
                D_flag=true;
                
            }
            else if(I_flag==true && operations[i][j]!=' '){
                abc+=operations[i][j];
            }
             else if(D_flag==true && operations[i][j]=='-'){ //최솟값삭제
                if(answer.size()>0)
                answer.erase(answer.begin());
                 break;
            }
            
            else if(D_flag==true && operations[i][j]=='1'){ //최댓값삭제
                if(answer.size()>0){
                    answer.erase(answer.begin()+answer.size()-1);
                }
            }
           
        }
        if(abc!=""){
            answer.push_back(stoi(abc));
 
        }
        sort(answer.begin(),answer.end());
    }
    
    if(answer.size()==0){
        result.push_back(0);
        result.push_back(0);
    }
    else{
    int N=answer.size();
  
    result.push_back(answer[N-1]);
    result.push_back(answer[0]);
    }
    return result;
}

https://www.acmicpc.net/problem/2589

코드 설명

BFS 기본문제 입니다.

BFS를 반복적으로 사용하여 거리가 가장 긴 구간을 완전탐색하여 구하는 문제였습니다.

가장 긴 거리를 재기위해 result라는 또하나의 map을 만들어주어서 거리를 기록하였습니다.

코드

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int N, M;
char map[51][51];
bool visited[51][51];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int result[51][51];
int maxx;
void bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;

	while (!q.empty()) {
		int y = q.front().first;
		int 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 || ny >= N || nx >= M) continue;
			if (!visited[ny][nx] && map[ny][nx]=='L') {
				q.push({ ny,nx });
				visited[ny][nx] = true;
				result[ny][nx] = result[y][x] + 1;
			}

		}



	}
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (maxx < result[y][x]) maxx = result[y][x];

		}
	}

}
int main() {
	cin >> N >> M;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];


		}


	}
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] == 'L'){
				memset(result, 0, sizeof(result));
				memset(visited, false , sizeof(visited));
				bfs(y, x);
			}
		}
	}
	cout << maxx;
	return 0;
}

https://www.acmicpc.net/problem/1260

코드 설명

DFS, BFS의 기본을 위해 다시 복습하였다. 아직까지도 vector를 사용하는 것보다 2차원 배열을 사용하는 게 편한 것 같다....

하지만 vector를 사용하여 링크드리스트 형태로 구현하는 것도 연습하자!

코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int N, M, V;
int map[1001][1001];
bool visited[1001];

void DFS(int start) {
	
	
	
	
	for (int i = 0; i <= N; i++) {
		if (map[start][i] == 1 && !visited[i]) {
			visited[i] = true;
			cout << i << " ";
			DFS(i);

		}


	}



}
void BFS(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int start = q.front();
		cout << start << " ";
		q.pop();

		for (int i = 0; i <= N; i++) {
			if (!visited[i] && map[start][i]) {
				q.push(i);
				visited[i] = true;
			}


		}

	}

}
int main() {
	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) {

		int a, b;
		cin >> a >> b;

		map[a][b] = 1;
		map[b][a] = 1;

	}
	cout << V << " ";
	visited[V] = true;
	DFS(V);
	memset(visited, false, sizeof(visited));
	cout << endl;
	
	
	BFS(V);








	return 0;
}

https://www.acmicpc.net/problem/1937

코드 설명

DP 메모리제이션 방식 + DFS을 합친 좋은 문제였던 것 같다.

어디 코테를 보면서 비슷한 걸 본 적이 있었는데 그 당시에 못 풀었어서 이문제는 복습을 계속해봐야 할 것 같다.

문제의 경우 DP맵 , 대나무 숲 맵 두 개로 나누어 서로 비교하며 문제를 풀어나가야 한다.

DP[y][x] : 그곳에서 시작하였을 때의 최대 이동 칸수 

즉, DP[y][x]에 값이 있다는 것은 굳이 들어가지 않아도 된다는 것을 의미한다. (이미 최대 경로가 들어가 있음)

이후에는 dfs(ny,nx)+1 을 통해 1씩 경로수를 늘려주며 재귀 탐색을 한다.

코드

//대나무먹고 자리옮기면 옮기려는 지역이 대나무가 더 많아야함(상하좌우)
//최댓값찾기
//전체탐색
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N;
int map[501][501];

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int dp[501][501];
int dfs(int y, int x) {
	
	if (dp[y][x]) return dp[y][x]; // dp map에 값이 있다면 탐색하지 않고 리턴
	dp[y][x] = 1; // 없으면 처음 1부터 시작

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		if (map[ny][nx] <= map[y][x]) continue;
		dp[y][x]= max(dp[y][x], dfs(ny, nx)+1);


	}

	return dp[y][x];  // 4방향 전부 작을때 기존 dp return


}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];

		}
	}

	int answer = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			answer = max(answer, dfs(y, x));
		}
	}

	cout << answer;



	return 0;
}