우주선 2월 전까지(~25/02/16)

[Jinsun-Lee]

전체 문제 리스트

[Jinsun-Lee]

• 노션 전체 내용 확인 끝
• 리드미에 갱신

• 기본 환경 세팅, 기초 문법 | 1970. 쉬운 거스름돈
• String 기초&응용 | 문자열 실버 문제
• DFS와 BFS
• DFS 개념 | 4008. [모의 SW 역량테스트] 숫자 만들기
• BFS 개념 | 순열 사이클
• 단계별로 풀어보기
• 메모이제이션
• 우선순위 큐 컵라면
• 바이너리 서치 나무 자르기
• 유니온 파인드 집합의 표현 | 여행 가자

[Jinsun-Lee]

• ⭐N과 M 시리즈
• ⭐코테합: 36번: 알파벳 그래프 노드 순회
• ⭐1260. DFS와 BFS
• ⭐5427. 불
  입력이 연결되어 있는 경우 cin.get()
• ⭐양과 늑대
• ⭐부분수열의 합
• 1473. 음식물 피하기
• 1012. 유기농 배추
• 주디와 당근 농장

[Jinsun-Lee]

기본 환경 세팅, 기초 문법 🔗

int map[4][6] = {}; // 지역에서 0으로 초기화

#include <algorithm>
int map[4][6];
fill(&map[0][0], &map[3][6], 2); //⭐[y-1][x]

sort(시작주소, 끝주소, greater<int>()); // 내림차순

bool cmp(int a, int b){
    return a > b;
}
sort(시작주소, 끝주소, cmp);

vector<int> vec(N, 1);
for (auto& i : vec) cout << i << " "; // vec.size()

vector<pair<int, int>> vec;
for (auto& i : vec) cout << i.first << " " << i.second << "\n";

vector<vector<int>> map(N, vector<int>(M, -1)); // N행 M열

vec.clear();
fill(vec.begin(), vec.end(), 1);

sort(vec.begin(), vec.end(), cmp); // bool cmp

void cmp(vector<int>& node){
    sort(node.begin(), node.end());
}
for_each(map.begin(), map.end(), cmp); //⭐sort 아니고, bool 대신 void

[Jinsun-Lee]

쉬운 거스름돈 🔗

dfs로 짜거나, 그냥 반복문이나... 큰 차이 없어

[Jinsun-Lee]

String 기초&응용 🔗

string b(a); // 문자열 복사

size_t index = str.find(targetStr, 0); // 문자열 찾기

reverse(str.begin(), str.end()); // 문자열 거꾸로

[Jinsun-Lee]

문자열 실버 문제 🔗

[Jinsun-Lee]

⭐1260. DFS와 BFS

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

int N,M,V;

// 자료 선언 형태 기억해
vector<vector<int>> nodeList;
vector<bool> visited;

// dfs 함수 형태도 틀리다니...
void dfs(int from){
	visited[from]=1;
	cout << from << " ";

	for(int i = 0; i < nodeList[from].size(); i++){
		int to = nodeList[from][i];
		if(visited[to]) continue;
		dfs(to);
	}
}

// bfs 함수 형태도 틀리다니...
void bfs(int start){
	queue<int> q;
	q.push(start);

	visited[start]=1;
	cout << start << " ";

	while(!q.empty()){
		int cur = q.front(); q.pop();

		for(int i = 0; i < nodeList[cur].size();i++){
			int to = nodeList[cur][i];
			if(visited[to]) continue;
			visited[to]=1;
			cout << to << " ";
			q.push(to);
		}
	}
}

// sort 함수 기억해
void compare(vector<int>& node){
	sort(node.begin(),node.end());
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	freopen_s(new FILE*,"input.txt","r",stdin);

	cin >> N >> M>> V;

	// 초기화 
	nodeList = vector<vector<int>>(N+1);
	visited = vector<bool> (N+1,false);

	int a,b;
	for(int i = 0; i < M; i++){
		cin >> a >> b;
		nodeList[a].push_back(b);
		nodeList[b].push_back(a);
	}

	// sort
	for_each(nodeList.begin(),nodeList.end(),compare);

	dfs(V);
	cout << "\n";
	visited = vector<bool> (N+1,false);
	bfs(V);

	return 0;
}

[Jinsun-Lee]

⭐코테합: 36번: 알파벳 그래프 노드 순회

• DFS로 모든 그래프의 노드 순회하기
• start 문자가 주어짐, graph는 출발, 도착 노드의 쌍
• 반환값은 그래프의 시작부터 모든 노드를 탐색한 경로가 저장된 배열
• 노드의 최대 개수는 100개를 넘지 않음
• 시작부터 모든 노드를 방문할 수 있는 경로가 반드시 있음
• 각 노드는 알파벳 대문자
• 시간복잡도는 O(간선의개수+노드의개수)
  인접리스트 생성할 때, 간선 개수만큼 연산해서 O(간선의수)
  탐색 시 모든 노드를 1번씩 방문하니까 O(노드의수)

vector<char> solution(vector<pair<char, char>> graph, char start) {

}

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

    // 출력값 : A B C D E
    print(solution({ {'A', 'B'}, {'B', 'C'}, {'C', 'D'}, {'D', 'E'} }, 'A'));

    init();

    //출력값 : A B D E F C
    print(solution({ {'A', 'B'}, {'A', 'C'}, {'B', 'D'}, {'B', 'E'}, {'C', 'F'}, {'E', 'F'} }, 'A'));

    return 0;
}

1. 인접리스트 생성 부분

// ⭐내 코드
vector<char> solution(vector<pair<char, char>> graph, char start) {
  for (int i = 0; i < graph.size(); i++) { // ⭐
      char u = graph[i].first; // ⭐
      char v = graph[i].second; // ⭐
      adjList[u].push_back(v); // ⭐
  }
  
  dfs(start); // ⭐
  return result;
}

vector<char> solution(vector<pair<char, char>> graph, char start) {
  for (auto& edge : graph) {
    char u = edge.first;
    char v = edge.second;
    adjList[u].push_back(v);
  }

  dfs(start);
  return result;
}

2. DFS

#include <iostream>
#include <iterator>
#include <vector>
#include <unordered_map> // ⭐사전순으로 탐색할 때 편하게
#include <unordered_set> // ⭐방문한 노드를 저장
using namespace std;

unordered_map<char, vector<char>> adjList; // ⭐
unordered_set<char> visited; // ⭐
vector<char> result;

void dfs(char node) {
  //❶ 현재 node를 방문한 목록 및 방문한 경로 추가
  visited.insert(node); // ⭐
  result.push_back(node); // ⭐

  //❷ 현재 node와 인접한 노드 중, 방문하지 않은 node들에 대해 깊이우선탐색을 계속 진행
  for (char neighbor : adjList[node]) { // ⭐
    if (visited.find(neighbor) == visited.end()) { // ⭐
      dfs(neighbor); // ⭐
    }
  }
}

// 내 코드
#include <iostream>
#include <iterator>
#include <vector>
#include <unordered_map> 
#include <unordered_set>
using namespace std;

#include <stack>
#include <algorithm>

unordered_map<char, vector<char>> adjList;
unordered_set<char> visited;
vector<char> result;


void dfs(char start) {
    stack<char> st;
    st.push(start);

    while (!st.empty()) {
        char cur = st.top();
        st.pop();

        // 방문한 적 없다면 방문 처리
        //if (visited.count(cur)) continue;
        if (visited.find(cur) == visited.end()) {
            visited.insert(cur);
            result.push_back(cur);

            // 사전 순으로 DFS를 보장하기 위해 역순으로
            vector<char>& neighbors = adjList[cur];
            sort(neighbors.rbegin(), neighbors.rend());

            // 현재 노드와 인접한 노드 중, 방문하지 않은 곳 탐색
            for (char neighbor : adjList[cur]) {
                if (visited.find(neighbor) == visited.end()) {
                    st.push(neighbor);
                }
            }
        } // if문 끝

    }
}

[Jinsun-Lee]

⭐5427. 불

입력이 연결되어 있는 경우

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        char input = cin.get();
        while (input == '\n') input = cin.get();
        map[i][j] = (int)(input-'0');

int N, M;
const int MX = 1002;
int map[MX][MX];
int d1[MX][MX];
int d2[MX][MX];

int main(){
    int tCase; cin >> tCase;
    while(tCase--){
        cin >> M >> N;

        for(int i = 0; i < N; i++){
            fill(d1[i],d1[i]+M,0);
            fill(d2[i],d2[i]+M,0);
        }

        queue<Node> q1 = {};
        queue<Node> q2 = {};

        char s;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                cin >> s;

                // 벽일 때
                if(s=='#') map[i][j] = -1;
                else {
                    if(s=='*'){
                        d1[i][j]=1;
                        q1.push({i,j});
                    }
                    else if(s=='@'){
                        d2[i][j]=1;
                        q2.push({i,j});
                    } 

                    // 벽이 아닐 땐 map을 0으로
                    map[i][j] = 0;
                }
            }
        }

        // 불부터 퍼트리기
        while(!q1.empty()){
            Node cur = q1.front();
            q1.pop();
            for(int i = 0; i < 4; i++){
                int ny = cur.y+dy[i];
                int nx = cur.x+dx[i];
                if(ny >=N || nx >=M || ny < 0 || nx < 0) continue;
                
                // 벽이거나 이미 퍼져있을 경우
                if(map[ny][nx]==-1 || d1[ny][nx]>0) continue;
                d1[ny][nx] = d1[cur.y][cur.x] + 1;
                q1.push({ny,nx});
            }
        }

        bool done=false;
        while(!q2.empty() && done==false){
            Node cur = q2.front();
            q2.pop();
            for(int i = 0; i < 4; i++){
                int ny = cur.y+dy[i];
                int nx = cur.x+dx[i];

                // 출력 범위 확인
                if(ny >=N || nx >=M || ny < 0 || nx < 0){
                    cout << d2[cur.y][cur.x] << "\n";
                    done = true;
                    break;
                }

                // 벽이거나, 내가 방문했으면 중단
                if (map[ny][nx]==-1 || d2[ny][nx]>0) continue;
                
                // ⭐불이 아예 오지 않거나, 불보다 먼저 갈 수 있다면 진행
                //if(d1[ny][nx]!=0 && d2[cur.y][cur.x]+1>=d1[ny][nx]) continue;
                if(d1[ny][nx]==0 || d2[cur.y][cur.x]+1<d1[ny][nx]){
                    d2[ny][nx] = d2[cur.y][cur.x] + 1;
                    q2.push({ny,nx});
                }
            }
        }        

        if (done==false) cout << "IMPOSSIBLE\n";
    }

    return 0;
}

[Jinsun-Lee]

⭐양과 늑대

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

const int MX = 18;

vector<int> nodeList[MX];
int visited[MX];

int sheep,wolf,mxSheep;

void dfs(vector<int> cur,vector<int> info){ //
    
    sheep = 0; wolf = 0;
    for(int i = 0; i < cur.size(); i++){ //
        if(info[cur[i]]==1) wolf++; //
        else sheep++;
    }

    if(sheep<=wolf) return;

    if(mxSheep<sheep){
        mxSheep = sheep; // 주의

        for(auto i : cur) cout << i << " ";
        cout << "\n";
    }

    for(int i = 0; i < cur.size(); i++){
        int nxt = cur[i];

        // 현재 노드와 인접한 노드를 순회
        for(int j = 0; j < nodeList[nxt].size(); j++){ // 주의
            if(visited[nodeList[nxt][j]]) continue; // 주의

            visited[nodeList[nxt][j]] = true;
            cur.push_back(nodeList[nxt][j]);
            dfs(cur,info);
            visited[nodeList[nxt][j]] = false;
            cur.pop_back();
        }
    }
}

int solution(vector<int> info,vector<vector<int>> edges) {

    // 연결 
    for(int i = 0; i < info.size()-1; i++){ // 주의
        nodeList[edges[i][0]].push_back(edges[i][1]); // 주의
    }

    // 주의
    dfs({0},info);

    return mxSheep;
}

// 여러 테스트
void init() {
    for(int i = 0; i < MX; i++) {
        nodeList[i].clear();
        visited[i] = 0;
    }
    mxSheep = 0;
}

int main() {
    // 5
    cout << solution({0,0,1,1,1,0,1,0,1,0,1,1},
        {{0,1},{1,2},{1,4},{0,8},{8,7},{9,10},{9,11},{4,3},{6,5},{4,6},{8,9}}
    ) << endl;

    init();

    // 5
    cout << solution({0,1,0,1,1,0,1,0,0,1,0},
        {{0,1},{0,2},{1,3},{1,4},{2,5},{2,6},{3,7},{4,8},{6,9},{9,10}}
    ) << endl;

    return 0;
}

[Jinsun-Lee]

⭐부분수열의 합

int n,s;
int a[21];
int ans = 0;

void dfs(int depth, int sum){
	if(depth >=n){
		if(sum==s) ans++;
		return;
	}

	dfs(depth+1,sum);
	dfs(depth+1,sum+a[depth]);
}

[Jinsun-Lee]

1473. 음식물 피하기

for (int i = 0; i < N; i++) {
	fill(map[i], map[i] + M, 0); 
	fill(visited[i], visited[i] + M, false);
}

map = vector<vector<int>>(N, vector<int>(M, 0));
visited = vector<vector<bool>>(N, vector<bool>(M, false));

[Jinsun-Lee]

1012. 유기농 배추

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

const int MX = 51;
int N,M,K;
int map[MX][MX];
bool visited[MX][MX];

struct Node {
    int y,x;
};

int dy[]={-1,0,1,0};
int dx[]={0, 1, 0, -1};

int main(){
    int tCase; cin >> tCase;
    while(tCase--){
        cin >> N >> M >> K;

        // 초기화
        for(int i = 0; i < N; i++){
            fill(map[i],map[i]+M,0);
            fill(visited[i],visited[i]+M,false);
        }

        int y,x;
        for(int i = 0; i < K; i++){
            cin >> y >> x;
            map[y][x]=1;
            //q.push({y,x});
        }

        int ans = 0;

        // 여기에 바로 while 때려넣을 거면 함수 써야 해
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(map[i][j]==1 && !visited[i][j]){
                    queue<Node> q;
                    q.push({i,j});
                    visited[i][j]=1;

                    while(!q.empty()){
                        Node cur = q.front();
                        q.pop();

                        //visited[cur.y][cur.x] = 1;
                        //ans++;

                        for(int i = 0; i < 4; i++){
                            int ny = cur.y+dy[i];
                            int nx=cur.x+dx[i];

                            if(ny >= N || nx >= M || ny <0 || nx <0) continue; // 범위에 등호도!!!
                            if(map[ny][nx]==0 || visited[ny][nx]) continue; // 조건에 map도 확인해야 해
                            visited[ny][nx]=1;
                            q.push({ny,nx});
                        }
                    }

                    ans++; // 여기에 추가!!! 
                }
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define Y first
#define X second 

using namespace std;

int m, n, k;
const int MX = 52;
int map[MX][MX];
bool visited[MX][MX];

int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };

queue<pair<int, int>> q;

void bfs(int y, int x) {
	q.push({ y, x });

	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cur.Y + dy[i];
			int nx = cur.X + dx[i];

			if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;

			if (map[ny][nx] == 1 && !visited[ny][nx]) {
				visited[ny][nx] = true;
				q.push({ ny, nx });
			}
		}
	}
}

int main() {
	int tCase; cin >> tCase;
	while (tCase--) {
		cin >> m >> n >> k;

		for (int i = 0; i < n; i++) { // 초기화 꼭 해
			fill(map[i], map[i] + m, 0); 
			fill(visited[i], visited[i] + m, false);
		}
		
		int x, y;
		for (int i = 0; i < k; i++) {
			cin >> x >> y;
			map[y][x] = 1;
		}

		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j]==1 && !visited[i][j]) { 
					visited[i][j] = true;
					bfs(i, j);
					cnt++;
				}
			}
		}

		cout << cnt << "\n";
	}
	return 0;
}

[Jinsun-Lee]

주디와 당근 농장

int main(){
        cin >> N >> R >> C;

        queue<Node> q;
        R=R-1; C=C-1;
        map[R][C]=1;
        visited[R][C]=1;
        q.push({R,C});

        int cnt=1;
        while(!q.empty()){
            Node cur = q.front();
            q.pop(); cnt++;

            for(int i = 0; i < 4; i++){
                int ny = cur.y+dy[i];
                int nx = cur.x+dx[i];

                if(ny >=N || nx >=N || ny < 0 || nx < 0) continue;
                if(visited[ny][nx] || map[ny][nx]>0) continue;
                visited[ny][nx] = true;
                map[ny][nx] = map[cur.y][cur.x] + 1;
                q.push({ny,nx});
            }
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(map[i][j]%2==1) cout << "v";
                else cout << ".";
            }
            cout << "\n";
        }
    }
    return 0;
}