백준 2589--c++

백준 2589--c++
문제 바로가기
1. 이러한 map형식은 bfs,dfs,dp를 이용하는것이 대부분이다.
2. 문제를 읽을때 최단거리로 이동한다는 말이 나온다.=>bfs이용
그렇다면 왜? dfs가 아닌 bfs를 사용해야하는 것일까?

이번 문제는 dfs를 사실 이용해도 괜찮다.
왜냐하면,
1. 주어진 N의 길이가 50으로 멀지 않다.
2. 어차피 모든 L을 다 뒤져야한다.

그러나 map의 크기가 크거나 해당 문제처럼 모든 L로 갈 수 있는 경우를 살피는 경우가 아닌 목적지가 항상 N,M으로 끝에 있는 경우라면, 굳이 dfs를 써서 왼쪽으로 갈 이유가 없다는 말이다.
dfs는 목적지가 반대여도 깊이 우선 탐색이니까 왼쪽도 전부 탐색해야하기 때문이다.
그러나 bfs는 인접노드를 먼저 탐색하기 때문에, 다음 노드를 방문할때 최단 거리가 보장이 된다.

그러므로 나는 bfs로 문제를 풀어보았다.
자 이제 이 문제를 어떤 알고리즘으로 풀어야할지 감을 잡았다.
그러면, 결국 모든 L에서 bfs로 최대 거리를 확인해야한다는것인데 이게 가능한지 확인해야한다. for문이 n^2이고 여기서 while문에서 또 있다. 그런데 모든 map이 L로 채워져있다고 하면, 모든 map을 방문하는 것과 같으므로, 이중for문으로 n^2일것이다.
그렇다면, 최대 아무리해도 n^4인데 n이 50이므로 시간제한이 1초인 1억번의 연산은 넘지 않는다.
고로 완전탐색과, 이분탐색을 둘다 사용하여야한다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int map[51][51] = { 0, };
int N, M;
int mymax = 0;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

//map받기
void makemap() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			char t;
			cin >> t;
			if (t == 'L') {
				map[i][j] = 1;
			}
			else {
				map[i][j] = 0;
			}
		}
	}
}


void BFS(int i, int j) {
	int cnt = 0;
    //방문을 하면 그전 노드까지 가는 비용+1로 visited갱신
	int visited[51][51] = {0,};
	queue<pair<int, pair<int, int>>>q;
    //처음에 0과, i,j를 push 그리고 방문처리
	q.push({ 0, {i, j} });
	visited[i][j] = 1;
	while (!q.empty()) {
		int cost = q.front().first;
		int x = q.front().second.first;
		int y = q.front().second.second;
		q.pop();
		for (int t = 0; t < 4; t++) {
			int nx = x + dx[t];
			int ny = y + dy[t];
			if (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny]==1 && visited[nx][ny]==0) {
				visited[nx][ny] = cost + 1;
				q.push({ cost + 1,{nx,ny} });
			}
		}
	}

//visited가 채워졌는데 이제 최댓값 확인하고 max와 비교
	for (int x = 0; x < N; x++) {
		for (int y = 0; y < M; y++) {
			if (visited[x][y] > cnt) {
				cnt = visited[x][y];
			}
		}
	}

	if (cnt > mymax) mymax = cnt;
}

int main() {
	cin >> N >> M;
	makemap();
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 1) {
				BFS(i, j);
			}
		}
	}
	cout << mymax;
}

어렵지 않은문제였다. 난이도 하