<문제의 접근>
0 또는 1로 이루어진 100 x 100 배열에 대해서 0을 1로 채워가면서 연결되는 최소길이를 구하는 문제이다. 어떻게 접근해야 할까? 일단 격자 형태로 좌/우/상/하를 탐색하는 문제의 경우에는 BFS부터 검토해 보는 것이 좋다. 보통의 BFS 문제가 격자를 바탕으로 이루어지기 때문이다. 이 문제도 확장 형태를 보면 BFS로 풀리는 문제라는 것은 어렵지 않게 유추할 수 있다. 다만, 어려운 점은 시작위치와 도착 위치를 어떻게 잡느냐이다.
시작 위치를 어디로 잡아야 할까? 문제에서 시작 위치와 도착 위치가 정해지는 경우는 시작위치를 queue에 넣고 탐색을 진행하되 도착 위치에서 탐색을 종료하면 된다. 그런데 이 문제는 시작 위치와 도착 위치가 불분명하다. 어떻게 시작해야 할까? 문제에서 제시되어 있는 1로 이루어진 섬이 어러개 존재할 수 있는 있는 상황이라서 특정한 시작지점과 도착 지점을 도출하기 어렵다. 이 문제는 모든 시작 위치와 모든 출발 위치를 탐색해야 하는 문제다.
<문제의 구성>
BFS의 기본 형식에 따라 모든 격자에서 확장을 검토한다. 즉, 2단 for문을 0부터 99까지 돌리는 형식이다. 그런데, 격자에서의 값이 1이 아닌 경우는? 섬이 아니기 때문에 skip한다. 그렇지 않다면 섬마다 각자 다른 번호를 부여하는 작업이 필요하다. 위의 예시로 본다면 왼쪽위의 섬(1 배열)은 값을 2로 변경하고, 오른쪽 위의 섬은 값을 3으로, 하단 중앙부는 4로 값을 변경해 주는 것이다. 이런 작업이 왜 필요할까? 이는 시작조건 & 종료조건과 관련되어 있다.
<시작조건 & 종료조건>
1로 상/하/좌/우로 연결되어 있는 땅은 같은 섬이다. 같은 섬과 다른 섬과의 차이가 필요하다. 섬의 번호는 2번 부터 차례로 매겨지며, 1로 연결되어 있는 모든 주변을 같은 섬으로 인식한다.(-> Phase 1) 주변의 연결된 모든 땅을 같은 섬으로 인식을 끝내면 바다인 (값이 0 인곳) 곳으로 확장을 시작한다. 이 때 0이 아닌 값이 발견될 때의 처음 거리가 최소 거리가 된다. (->Phase 2). 격자의 모든 곳을 돌며 위의 Phase 1과 Phase 2를 번갈아 가면서 계속 진행하면서 최소 거리를 갱신해 나간다. 섬의 번호가 모두 다르기 때문에 시작 위치와 종료 위치가 번호로 구별되며, 모든 격자 탐색을 마치면 모든 섬간의 거리가 비교되면서 최소거리가 구해지게 된다.
<BFS 구현 코드>
python의 경우는 BFS 구현의 위해서 deque를 이용한다. python은 tuple이라는 형식으로 인해서 인자의 개수가 몇개라도 괄호로 묶어서 쉽게 표현할 수 있는 장점이 있다. q1의 경우는 현재 섬의 영역을 확인하기 위해서 필요한 deque이고, q2는 현재 섬의 위치와 거리를 0으로 세팅하고 추후에 활용하게 되는데 필요한 deque이다. 순차적으로 while 문을 2번 돌리게 되는데 첫번째는 현재 섬의 위치 확인 및 섬의 값 변경을 진행하고, 두번째 while문은 다른 섬까지의 최소 거리를 구하기 위한 작업을 진행하게 된다.
def bfs():
cat = 1
sol = 10_000
for i in range(n):
for j in range(n):
if arr[i][j] == 1: # arr[i][j] == 0이면 바다 이므로 skip
cat += 1 # 섬번호 category
q1 = deque([(i,j)]) # 현재 섬의 영역 확인
q2 = deque([(0,i,j)]) # 다른 섬과의 거리를 확인 하기 위한 queue
arr[i][j] = cat # 현재 섬번호 저장
while q1: # 현재 섬 영역 확인 및 다른섬과의 거리 0으로 초기화
y, x = q1.popleft()
for k in range(4):
ny, nx = y + dy[k], x + dx[k]
if not (0<=ny<n and 0<=nx<n): continue
if arr[ny][nx] != 1: continue
q1.append((ny, nx))
q2.append((0, ny, nx))
arr[ny][nx] = cat
check = [[0]*100 for _ in range(100)] # visit 배열
flag = False
while q2: # 현재 섬에서 다른 섬으로의 거리 파악
cost, y, x = q2.popleft()
# check[y][x] = 1
if flag or (cost >= sol):
break
for k in range(4):
ny, nx = y + dy[k], x + dx[k]
if not (0<=ny<n and 0<=nx<n): continue
if check[ny][nx]: continue
if arr[ny][nx] != 0:
if arr[ny][nx] != cat:
sol = min(sol, cost)
flag = True
break
else:
continue
q2.append((cost+1, ny, nx))
check[ny][nx] = 1
return sol
C++도 같은 형식으로 구현하게 되지만, C++은 형식에 명확하게 제한을 받는다. python과 진행의 흐름은 공유하지만, queue에 들어가는 형식에 따라서 2개(y 위치, x위치)일 경우는 pair<int, int>를 사용하고, 3개(distance, y위치, x위치)일 경우는 tuple<int, int, int>를 사용했다. 그 외의 흐름은 거의 동일하다. python도 마찬가지 이야기인데, 주의해야 할 부분은 두번 째 while문의 arr[ny][nx] !=0일때 이다. 만약 arr[ny][nx]가 현재의 섬 번호와 같지 않다면 현재 섬과 다른 섬간의 최소 거리가 나타났다는 뜻이다. while문을 종료하면 심플하다. 그런데 arr[ny][nx]가 현재의 섬 번호와 같다면? 여기가 약간 해깔리는 부분인데, 그냥 아무런 액션을 위치하지 않고 다음으로 넘어가는 continue로 구현하면 된다. 아래 코드를 보면 알겠지만, continue를 해주지 않으면 arr[ny][nx]가 0인 것과 같은 routine으로 돌기 때문에 오답을 도출하게 된다.
int bfs() {
int cat = 1;
int sol = 10000;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++) {
if (arr[i][j] != 1) continue; // 1이 아니라면 탐색 시작할 필요 없음
cat += 1; // group categorizing index, 2번 부터 형성
deque<pair<int, int>> q1; // BFS 그룹 형성을 위한 배열
deque<tuple<int,int, int>> q2; // BFS 현재 그룹 queue
q1.push_back(make_pair(i,j));
q2.push_back(make_tuple(0,i,j));
arr[i][j] = cat; // 그룹 원소 배열 형성
while (q1.size()) {
int y, x, ny, nx;
y = q1.front().first;
x = q1.front().second;
q1.pop_front();
for (int k=0;k<4;k++) {
ny = y+dy[k];
nx = x+dx[k];
if ((ny<0) || (ny>=n) || (nx<0) || (nx>=n)) continue;
if (arr[ny][nx] != 1) continue;
q1.push_back(make_pair(ny,nx));
q2.push_back(make_tuple(0,ny,nx));
arr[ny][nx] = cat;
}
}
fill(&check[0][0], &check[99][100], false);
bool flag = false;
while (q2.size()) {
int cost, y, x, ny, nx;
cost = get<0>(q2.front());
y = get<1>(q2.front());
x = get<2>(q2.front());
q2.pop_front();
if (flag || (cost >= sol)) break;
for (int k=0;k<4;k++) {
ny = y + dy[k];
nx = x + dx[k];
if ((ny<0) || (ny>=n) || (nx<0) || (nx>=n)) continue;
if (check[ny][nx]) continue;
if (arr[ny][nx] != 0) {
if (arr[ny][nx] != cat) {
sol = min(sol, cost);
flag = true;
break;
}
else continue;
}
q2.push_back(make_tuple(cost+1, ny, nx));
check[ny][nx] = true;
}
}
}
}
return sol;
}
그 외에는 문제의 구성만 제대로 구현할 수 있다면 크게 어려운 부분은 없을 것이다. Python과 C++로 구현하면 언제나 느끼는 일이지만, C는 정말로 적은 메모리와 시간을 사용하는 것을 아래와 같이 확인해 볼 수 있다. 그렇다고 C++이 좋다는 이야기일까? Algorithm에 한해서는 그렇다. 대용량 데이터를 처리해 보면, 절대 그렇지 않으니까. language는 tool에 불과하다. 작업에 효율적인 language를 사용하는 것이 맞다.
전체 코드를 공유한다.
<C++> https://github.com/Koo82/Algotirhm/blob/main/%5BBFS%5DBJ_2146.cpp
GitHub - Koo82/Algotirhm
Contribute to Koo82/Algotirhm development by creating an account on GitHub.
github.com
<Python> https://github.com/Koo82/Algotirhm/blob/main/%5BBFS%5DBJ_2146.py
GitHub - Koo82/Algotirhm
Contribute to Koo82/Algotirhm development by creating an account on GitHub.
github.com