[백준-6087] 레이저 통신


기존의 풀던 BFS와 살짝 다른 풀이법 이다.

메모리를 많이 사용하지 않았나 생각되긴 해서 다른 풀이법을 강구해 봐야겠다.

Code


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

int W, H;
char map[101][101];
bool check[101][101];
int dit[101][101];
vector<pair<int, int>> v;
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };

void bfs() {
	int sy = v[0].first, sx = v[0].second;
	queue<pair<int, int>> q;
	q.push({ sy,sx });
	check[sy][sx] = true;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			while (ny >= 0 && ny < H && nx >= 0 && nx < W) {
				if (map[ny][nx] == '*') break;
				if (!check[ny][nx]) {
					check[ny][nx] = true;
					dit[ny][nx] = dit[y][x] + 1;
					q.push({ ny,nx });
				}
				ny += dy[dir];
				nx += dx[dir];
			}
	
		}
	}
}


int main() {
	scanf("%d %d", &W, &H);
	for (int i = 0; i < H; i++) {
		scanf("%s", map + i);
		for (int j = 0; j < W; j++) {
			if (map[i][j] == 'C') v.push_back({ i, j });
		}
	}

	bfs();
	printf("%d\n", dit[v[1].first][v[1].second] - 1);
	return 0;
}





© 2020. by Andyworkingholiday

Powered by aiden