[PS/탐색/BFS/DFS] 여기저기 이곳저곳 탐색탐색 2

//이 글은 이곳의 문제들을 쭉 풀며 탐색의 기본을 다지는 과정을 적었습니다.

#1 백준 1260번 DFS와 BFS

DFS와 BFS의 Hello World! 정도의 문제.
하지만...난 이것조차 간단히 풀지 못했다. 그래도 푸는 과정에서 개념 정리가 확실하게 된듯해서 좋았던 문제!
먼저, 내 기억속의 BFS와 DFS를 더듬더듬 하며 코드를 작성했다.

void DFS(int v) {
	visited[v] = 1;
	cout << v << ' ';
	for (int i = 0; i < graph01[v].size(); i++) {
		int next = graph01[v][i];
		if (visited[next] == 0 ) {
			DFS(next);
		}
	}
}

void BFS(int v) {
	queue<int> q;
	q.push(v);
	visited2[v] = 1;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		cout << x << ' ';
		for (int i = 0; i < graph01[x].size(); i++) {
			int next = graph01[x][i];
			if (visited2[next] == 0) {
				q.push(next);
				visited2[next] = 1;
			}
		}
	}

정수형 visited, visited2 배열을 선언해 각각 방문여부를 적었고, 첫번째 케이스는 무난하게 통과하는듯 싶었다.

하지만,,,, 두번째 테스트 케이스에서는 ㅠㅠ..

..?무엇이 문제죠..? 알고리즘은 문제가 없는것 같은데요??? 저는 배운 그대로 썼어요!!!
문제는 입력부에 있었다.

	for (int i = 0; i < M; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		graph01[tmp1].push_back(tmp2);
        //graph01[tmp2].push_back(tmp1); <-간단히 요놈만 추가해주면 되는 문제였다.
	}

graph01은 인접리스트로 구현해 놓은건데, 포인트는 이게 양방향 그래프였다는 점이다.
양방향 그래프는 간선을 추가해줄때 양 정점을 링크시켜줘야 한다.
저 코드대로라면, 5와 1을 링크시킬떄, 5에서 1로 가는 간선은 있지만 1에서 5로 가는 간선은 없다는 얘기.

허나 문제는 그뿐만이 아니었는데..

??? 저기요?

이번에는 순서가 문제였다. 
정점을 방문할때 특별한 규칙이 없다면 값이 적은 정점부터 방문하는게 일반적이고, 이 문제에서도 그걸 요구하고 있다.
그래..내 코드는 정렬같은건 하지 않았지. 
정렬만 한다면 간단히 해결 될 문제지만, 난 c++에서 제공하는 sort() 함수의 문제점때문에 즐겨 사용하진 않는다.

(c++의 sort()는 퀵정렬이지만, 배열의 크기가 원래와는 달라질 수 있고, 그로인해 인덱스도 불규칙해 질 위험성이 있다. 이는 전체탐색할때는 문제가 없을수도 있지만, 공간복잡도나 인덱스를 직접 접근할때나 여러모로 위험하다고 생각한다.)

sort()를 써서 해결했다.

	for (int i = 1; i <= N; i++) {
		sort(graph01[i].begin(), graph01[i].end());
	}

음 뭐 그래요. 썩 맘에 들지는 않지만...

하지만 sort()를 쓰고싶지는 않았다.
다른 방법은 없을까 생각하다가, 인접행렬을 사용하면 좋을것 같다는 생각이 번쩍!
인접행렬은 인덱스에 직접 접근해 간선을 추가해 주는 식이기 때문에, 반복문을 돌릴때 낮은 인덱스부터 탐색한다면
정렬과정이 굳이 필요 없을것 같다는 생각이 들었다.
바로 실천해보자!

int graph[1001][1001] = { 0 }; //입력 크기가 1000까지 이기 때문에 큰 문제는 없을듯 싶다.

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

	for (int i = 0; i < M; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		graph[tmp1][tmp2] = 1;
		graph[tmp2][tmp1] = 1;
	}
    
	DFS(V);
	cout << endl;
	BFS(V);
}

void DFS(int v) {
	visited[v] = true;
	cout << v << ' ';

	for (int i = 1; i <=N; i++) {
		if (graph[v][i]&& !visited[i]){
				DFS(i);
		}
	}
}

void BFS(int v) {
	queue<int> q;
	q.push(v);
	visited2[v] = 1;

	while(!q.empty()){
		int x = q.front();
		q.pop();
		visited2[x] = true;
		cout << x << ' ';
		for (int i = 1; i <= N; i++) {
			if (graph[x][i] && !visited2[i]) {
					q.push(i);
					visited2[i] = 1;
			}
		}
	}
}

코드를 짜던 중, 인접행렬은 인접 리스트와는 다르게
다음 방문할 정점의 번호를 저장해주는 next등의 변수가 필요 없을것 같다는 생각이 들었고, 그것은 아마 옳은 생각이었던것 같다.
인접 리스트는 간선이 연결되어 있으면 바로 다음 정점의 번호를 알려주지만, 인접행렬은 단순히 정점간의 간선유무만 알려줌과 동시에 이미 반복문 안에 그 역할을 하는 변수가 있으므로,,,

문제 없군요 호호

성공

#2 백준 1303번 전쟁 - 전투

어려워 보이지 않았지만...조금 해맸다.
많은 탐색 문제들이 flood fill 알고리즘으로 해결되는 경우가 많다.
이 문제도 flood fill 알고리즘의 응용인듯.
(flood fill 알고리즘은 이곳에서 살펴볼수 있다. 구현은 DFS / BFS 둘 다 가능하다고 한다.)

구상은 간단. 각 좌표별로 flood fill 알고리즘을 돌려서 각 단계가 끝나면 병사수의 제곱을 결과값에 저장하면 끝.
하지만 이 문제는 함정이 있었으니..

정방은 잘 나옵니다.

...?먼가 이상하네요

바로 입력부를 잘못 만들었다(....)
항상 이런 문제를 풀 때에는 가로세로 입력을 주의할것!
이것때문에 알고리즘에 무슨 문제가 있는지 한참 해맸다. 그냥 입력만 바꿔주면 됐던 간단한 실수가 몇시간을 잡아먹었는지..

#include <iostream>
#include <stdio.h>

using namespace std;


int N, M, resultW = 0, resultB = 0;

char map[101][101] = { 0, };

bool visited01[101][101] = { 0, };
bool visited02[101][101] = { 0, };


int DFSW(int x, int y) {
    if (x<0 && x>N && y<0 && y>M && map[x][y] == 'B')
        return 0;

    if (map[x][y] == 'W' && visited01[x][y] == false) {
        visited01[x][y] = true;
        return DFSW(x + 1, y) + DFSW(x - 1, y) + DFSW(x, y + 1) + DFSW(x, y - 1) + 1;
    }

    return 0;

}
int DFSB(int x, int y) {
    if (x<0 && x>N && y<0 && y>M && map[x][y] == 'W')
        return 0;

    if (map[x][y] == 'B' && visited02[x][y] == false) {
        visited02[x][y] = true;
        return DFSB(x + 1, y) + DFSB(x - 1, y) + DFSB(x, y + 1) + DFSB(x, y - 1) + 1;
    }

    return 0;

}

int main() {

    cin >> N >> M;

    cin.ignore();

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            char tmp = '0';
            scanf("%c", &tmp);
            map[i][j] = tmp;
        }
        cin.ignore();
    }



    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (!visited01[i][j]) {
                int tmp01 = DFSW(i, j);

                tmp01 = tmp01 * tmp01;

                resultW += tmp01;

            }
            if (!visited02[i][j]) {
                int tmp02 = DFSB(i, j);
                tmp02 = tmp02 * tmp02;
                resultB += tmp02;
            }
        }
    }


    cout << resultW << ' ' << resultB << endl;

    return 0;
}

함수를 하나만 쓸수 있었지만 귀찮아서 그냥 나누었습니다. 헤헤

성공!

 

#3 백준 2178번 미로 탐색

탐색의 가장 기본적인 문제!
원트로 클리어했기때문에 풀고나서 기분이 정말 좋았다 ㅎㅎㅎ
탐색에서 최단거리를 구하는 문제는 주로 BFS를 이용하면 편하다.
DFS의 재귀구조는 이런 간단한 문제도 입력이 커지면 시간복잡도가 급격하게 늘어나기 때문에, 스택오버플로등의 문제를 야기할수 있다.

int BFS(int x, int y) {

	queue<pair<int, int>> q;

	q.push(pair<int, int>(x, y));

	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		if (x == N - 1 && y == M - 1) break;
		q.pop();

		visited[x][y] = true;

		for (int i = 0; i < 4; i++) {
			if (maze[x + dx[i]][y + dy[i]] !=0 //최단거리가 이미 구해진 칸이거나
				&& x + dx[i] >= 0		//미로를 넘어서는 칸이거나
				&& x + dx[i] < N
				&& y + dy[i] >=0
				&& y + dy[i] < M
				&&!visited[x + dx[i]][y + dy[i]]) { //이미 방문한 칸이거나
				q.push(pair<int, int>(x + dx[i], y + dy[i]));
				visited[x + dx[i]][y + dy[i]] = true;
				maze[x + dx[i]][y + dy[i]] = maze[x][y] + 1;
			}
		}
	}

	return maze[N - 1][M - 1];
}

좌표를 이용해서 푸는 문제는 c++에서 제공하는 utilty 헤더의 pair와 queue를 섞어 사용하면 풀기 용이하다.
pair는 한 쌍의 데이터를 가진 객체를 큐에 넣어주는데 사용한다.
구상은 간단. BFS와 같은 알고리즘에 십자방향으로 탐색하며 벽 등의 제한이 걸려있는 칸은 큐에 넣지 않는 식이다.
미로의 우측 최하단 칸에 최단거리가 구해져 있으므로, 최하단 칸의 값을 리턴!

헤헤 원트에 깨버렸지롱

성공!