[TIL] 21-07-05

알고리즘 스터디

• 백준 5557 1학년 O
• 백준 14226 이모티콘 ~

⚡깃허브 잔디 심기 오류 해결

• 깃허브 저장소에 push 했지만, 잔디 밭에 변화가 없었다

• git repository email과 local email이 다를 경우 이런 현상이 일어날 수 있다고 한다
  -> git repository email 확인: 깃허브 -> Settings -> Emails
  -> local email 확인: 소스트리에서 터미널 -> $ git config — list

• 확인해보니 하나는 네이버 이메일 주소를, 하나는 gmail 주소를 사용하고 있었다
  : Settings -> Emails -> Add email address로 메일 주소를 추가하여 해결하였다

📌참고자료

• 깃허브(github) 잔디심기 오류 해결
• Git push 했는데 잔디가 안심어질 때

📌참고자료

• DFS와 BFS의 활용

DFS가 역량테스트에서 주로 사용되는 방식

• 연결된 그래프의 완전 탐색
• 특정 조합을 뽑는 경우에 사용된다
  -> 주로 C++/JAVA에서 순열과 조합을 구현할 경우에 사용

BFS가 역량테스트에서 주로사용되는 방식

• 연결된 그래프의 완전 탐색
• 특정 그래프에서 가중치가 모두 같은 경우의 최단거리를 찾을 수 있다
  -> 가중치가 모두 같은 최단 거리 문제의 예:
  한 칸을 가는 데 1초가 걸리는 경우, 거리가 1인 경우, 등등
  -> BFS는 탐색 진행시 트리의 level별로 진행이 된다
  

• C++ BFS 구현

BFS 구현

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
//
// 노드 수: N, 간선 수: M, 시작 노드: S
int N, M, S;
// adjList[i]: 노드i와 인접한 노드들의 집합
vector<int> adjList[1001];
// isVisited[i]: 노드i의 방문 여부 기록 
bool isVisited[1001] = {0};
queue<int> que;
//
void bfs(int V) {
    // 루트 노드 삽입
    que.push(V); 
    //
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
        // 이미 방문한 노드라면 건너 뛰기
        if (isVisited[cur]) { continue; }
        // 방문하지 않은 노드라면 방문 표시
        isVisited[cur] = true;
    	//
        printf("%d ", cur);
        // 인접 노드들 큐에 삽입
        for (int i=0; i<adjList[cur].size(); i++) { 
            int next = adjList[cur][i];
            que.push(next);
        }
    }
}
//
int main() {
    scanf("%d %d %d", &N, &M, &S);
    // M개의 간선 입력 받기
    for (int i=0; i<M; i++) {
        // 간선의 양끝 노드 s, e
        int s, e;
        scanf("%d %d", &s, &e);
        adjList[s].push_back(e);
        adjList[e].push_back(s);
    }
    // sort
    for (int i=0; i<1001; i++) {
        sort(adjList[i].begin(), adjList[i].end());
    }
    // 방문 여부 초기화
    fill_n(isVisited, 1001, false); 
    // 시작 노드부터 너비 우선 탐색
    bfs(S);
    return 0;
}