백준 저지의 BFS 문제 풀이 과정을 공유드린다.
문제 출처

1. 문제설명

대표적인 길찾기 문제의 유형과 비슷하다.
처음에 문제를 잘못 이해해서 아기상어 간 최단 거리를 구하는 줄 알았으나, 아니었다.
요약하자면, 1에 해당하는 상어가 가는 거리를 갱신하고, 그 값의 최대 거리를 구하는 것이다.
상, 하, 좌, 우 외에 대각선이 추가된다.

2. 알고리즘 설계

1번 예제

아기 상어의 위치(x, y)를 기억해둔다.
- 본인은 pair<int, int>로 저장
하나씩 꺼내서 가중치를 1을 부여하여 맵을 갱신한다.
만약 이미 맵이 갱신되어 있다면, 더 작은 값을 넣는다
- (큐에서 꺼낸 위치의 값 + 1)과 다음 위치의 값 중 더 큰 값으로 갱신하면 됩니다.
결과

3. 로직

처음에 단순 BFS로 하려니 생각보다 코드가 지저분했습니다.
그래서 고민을 하다가 현재의 큐 사이즈만큼 돌리면 간단히 풀리는 문제였습니다.
- 이것만 이해하면 나머지는 일반적인 BFS 문제랑 똑같습니다.

  int sz = q.size();
  while(sz--) {
    pair<int, int> cur = q.front()
    ......
  }

이후, 큐에서 하나씩 꺼내서 8방향(상하좌우 + 대각선)을 탐색한다.
다음 위치로 갈 수 있다면, 다음 위치의 현재 값과 갱신될 값 중 큰 값을 넣는다.
맵의 가장 큰 값에서 1을 뺀 값을 정답으로 제출한다.
- 많은 분들이 1을 0으로 바꾸고 진행하는 것을 보았는데, 저는 나중에 1을 빼주는 게 코드가 더 깔끔하더라구요.

전체 코드

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

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

int n, m;
int map[50][50];

const int dy[] = { -1,1,0,0,-1,1,-1,1 };
const int dx[] = { 0,0,-1,1,-1,-1,1,1 };

int bfs() {
	int ans = 0;

	while (!q.empty()) {
		int sz = q.size();
		while (sz--) {
			pii cur = q.front();
			q.pop();

			for (int dir = 0; dir < 8; dir++) {
				int ny = cur.first + dy[dir];
				int nx = cur.second + dx[dir];

				if (ny < 0 || nx < 0 || ny >= n || nx >= m)
					continue;
				if (map[ny][nx] == 0) {
					map[ny][nx] = map[cur.first][cur.second] + 1;
					q.push({ ny, nx });
				}
				else {
					int comp = map[cur.first][cur.second] + 1;
					map[ny][nx] = (map[ny][nx] < comp) ? map[ny][nx] : comp;
				}
				ans = (ans > map[ny][nx]) ? ans : map[ny][nx];
			}
		}
	}

	return ans;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1)
				q.push({ i, j });
		}

	cout << bfs() - 1;
	return 0;
}

BOJ 17086번

1. 문제설명

2. 알고리즘 설계

3. 로직