백준으로 C++ 공부 24일차 (2667, 6064, 7569, 11286, 11403, 16928)

정확히 24일차는 아니지만 블로그 쓰는 횟수가 24번쨰이므로 그렇다고 치자

최근 싸지방을 잘 이용하지 못해 자주 못옴 ㅠㅠ

 

오늘 공부한 백준 (2667, 6064, 7569, 11286, 11403, 16928)

 

이제 BFS에 꽤나 익숙해졌다. 혼자서 구현할 수 있는 정도

내일부터는 골드 5문제들을 풀게 될 것이다. (아직 실버 몇개 안 푼게 있지만)

---

큐의 갯수를 세야 할 때 자주 썼다.

typedef pair<int, int> pii;
queue<pii> q;

---

문제의 input이 이런 식으로 가로로 빈칸 없이 나올 때

10101101
00110101
00011010
11010110

아래와 같이 string으로 받은 다음에 int형으로 다시받는 방법을 쓴다.

아니면 그냥 string으로 받아서 string으로 계속 풀수도 있다.

for (int i = 0; i < N; i++) {
	string tmp;
	cin >> tmp;
	for (int j = 0; j < N; j++)	
        map[i][j] = tmp[j] - '0';
}

 

플로이드-와샬 알고리즘을 이용해 11403 경로찾기 풀기

void floyd(void) {
    //i->j로 가는 길이 없어도
    //k를 거쳐갈 수 있으면 갈 수 있다고 여긴다
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][k] == 1 && map[k][j] == 1)
                    map[i][j] = 1;
            }
        }
    }
}

 i 에서 j 로 이동하는데 거리가 k를 거쳐서 가는게 더 빠른 경우를 이용한다.

아직 혼자서 풀 때 이용하지는 못할 듯