작은시작

www.acmicpc.net/problem/2178

코드 설명

 bfs를 이용하여 map[][] 이 1일 때만 탐색하면서 기존 좌표에 +1을 해준다( ++을 하면 전부 증가하므로 오류)

도착 좌표에 도착하면 출력

입력이 빈칸이없기 때문에 string으로 받은 후 한 칸씩 int 형 변환하여 넣어주었다.

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int map[101][101];
int N, M;

bool visited[101][101];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
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] == 1) {
				map[ny][nx] = map[y][x]+1;
				q.push({ ny,nx });
				visited[ny][nx] = true;
			}
		}

	}

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


	for (int y = 0; y < N; y++)
	{
		string abc;
		cin >> abc;
		for (int i = 0; i < abc.size(); i++) {
			map[y][i] = abc[i] - '0';
		}
	}
	bfs(0, 0);
	cout << map[N - 1][M - 1];


	return 0;
}

www.acmicpc.net/problem/7562

코드 설명

BFS기본 틀을 이용하여 풀었다. 출발좌표(sy,sx), 도착좌표(ty,tx) 를 담아줘서 bfs를 돌렸다.

조심해야할점은 최소 몇 번만에 이동하는지 물어봤기 때문에 queue에 cnt+1을 담아줘서 갈수있는 모든방향에 +1을 해주는 식으로 해줘야한다 

cnt++을 해주면 모든방향을 ++해주기때문에 답을 찾을 수 없다.

코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int map[301][301];
int N;//테스트케이스 개수 

bool visited[301][301];
int dy[] = { -2,-2,-1,-1,1,1,2,2 };
int dx[] = { -1,1,-2,2,-2,2,-1,1 };
int bfs(int sy, int sx, int ty, int tx,int a) {
	if (sy == ty && sx == tx) {
		return 0;
	}
	queue<pair<pair<int, int>,int>> q;
	q.push({ { sy,sx }, 0 });
	visited[sy][sx] = true;

	while (!q.empty()) {
		
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cnt = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= a || nx >= a) continue;
			if (ny == ty && nx == tx) {
				return cnt + 1;
			}
			if (!visited[ny][nx]) {

				q.push({{ ny,nx }, cnt + 1
			});
				visited[ny][nx] = true;
			}

		}

	}

}
int main() {
	cin >> N;
	vector<int> answer;
	for (int i = 0; i < N; i++) {
		memset(map, 0, sizeof(map));
		memset(visited, false, sizeof(visited));
		int cnt = 0;
		int a;
		cin >> a;
		int y, x;
		cin >> y >> x;//시작
		int ty, tx; //도착
		cin >> ty >> tx;
		cnt = bfs(y, x,ty,tx,a);
		answer.push_back(cnt);

	}
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << endl;
	}

	return 0;
}

www.acmicpc.net/problem/2644

BFS 코드

촌수를 찾는다는건 가장 짧은 거리를 찾는 것과 같다고 볼 수있으므로 BFS를 이용할 수있다.

if (map[abc][i] == 1 && arr[i] == 0)

arr배열을 통해 거리값들을 받으면서 지나오지않은 노드만 queue에 넣어준다.

#include<iostream>
#include <queue>
using namespace std;
int N, X, Y, M;
int map[101][101];
int arr[101];
void bfs(int start, int end) {
	queue<int> q;
	q.push(start);
	arr[start] = 1;
	
	while (!q.empty()) {
		int abc = q.front();
		q.pop();
		for (int i = 1; i <= N; i++) {//다음노드탐색
			if (map[abc][i] == 1 && arr[i] == 0) { //부모가 될수 있는가 + 이미 다녀온 노드 아닌경우 
				q.push(i);
				arr[i] = arr[abc] + 1;
			}
		}

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

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;

	}
	bfs(X, Y);

	if (arr[Y] != 0) {
		cout << arr[Y];
	}
	else cout << -1;




	return 0;
}

DFS 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, X, Y, M;
int map[101][101];
int visited[101];
bool flag;
int cnt;
void dfs(int p, int s,int level,int before) { //이전값 들고다니기 
	if (p == s) {
		flag = true;
		cnt = level;
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (map[p][i] == 1) {
			if (i == before) continue; 	//양방향 트리이므로 cycle을 방지하기위해 before

			dfs(i, s, level + 1,p);
		}

	}

}

int main() {
	cin >> N >> X >> Y >> M;

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;

	}


	dfs(X,Y,0,0);
	if (cnt == 0) cout << -1;
	else cout << cnt;


	return 0;
}

www.acmicpc.net/problem/2667

코드 설명

프로그래머스 대비 map을 전역변수로  주지않고 풀어보았다.

문제는 단순한 bfs+visited 배열을 이용하였다.

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int bfs(int map[][30],bool visited[][30],int y,int x,int N) {
	int cnt = 1;
	int dx[] = { -1,1,0,0 };
	int dy[] = { 0,0,1,-1 };
	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 >= N) continue;
			if (!visited[ny][nx] && map[ny][nx] == 1) {
				q.push({ ny,nx });
				visited[ny][nx] = true;
				cnt++;
			}
		}


	}
	return cnt;
}
int main() {
	int map[30][30];
	bool visited[30][30];
	memset(map, 0, sizeof(map));
	memset(visited, false, sizeof(visited));
	int N;
	cin >> N;

	for (int y = 0; y < N; y++) {
		string abc;
		cin >> abc;
		for (int x = 0; x < N; x++) {
			map[y][x] = abc[x] - '0';
		}
	}
	vector<int> answer;
	int k = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 1 && !visited[y][x]) {
				k++;
				int cnt=bfs(map,visited,y,x,N);
				answer.push_back(cnt);
			}
		}
	}
	cout << k << endl;
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << endl;
	}
	return 0;
}