#31 백준 1388번 C
우보만리
- visited 배열을 만들어 탐색 된 위치를 표시해 중복 탐색을 방지함
- BFS를 반복해서 수행하며 연결된 영역들을 찾는 Flood Fill 문제
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| char map[50 + 10][50 + 10], visited[50 + 10][50 + 10]; | |
| int N, M; | |
| // queue 정의 | |
| typedef struct { | |
| int r, c; | |
| }QUE; | |
| QUE q[50 * 50]; | |
| int rp, wp; | |
| QUE front(void) { return q[rp]; } | |
| void pop(void) { rp++; } | |
| void push(int r, int c) { | |
| q[wp].r = r; | |
| q[wp].c = c; | |
| wp++; | |
| } | |
| int empty(void) { return rp == wp; } | |
| // 조건 입력받는 함수 | |
| int inputData(void) { | |
| scanf("%d %d", &N, &M); | |
| for (int i = 0; i < N; i++) { | |
| scanf("%s", map[i]); | |
| } | |
| } | |
| // 시작 위치를 입력받아 탐색하는 BFS 함수 | |
| int BFS(int r, int c) { | |
| // queue 초기화 | |
| rp = 0; | |
| wp = 0; | |
| // 1. 탐색 시작점 queue에 push & visited 표시 | |
| push(r, c); | |
| visited[r][c] = 1; | |
| // 2. 탐색 (pop & expand) | |
| while (!empty()) { | |
| // 2-1. queue의 가장 앞의 데이터를 pop | |
| QUE cur = front(); pop(); | |
| // 2-2. pop 된 값과 연결된 node를 push할지를 판단 | |
| // cur 위치 값에 따라 column 방향일지 row 방향일지 결정됨 | |
| QUE np; | |
| np.r = cur.r; | |
| np.c = cur.c; | |
| if (map[cur.r][cur.c] == '-'){ | |
| np.c++; | |
| } | |
| else { | |
| np.r++; | |
| } | |
| // boundary 조건에 맞지 않는 경우 예외 처리 | |
| if (np.r >= N || np.c >= M) continue; | |
| else if (map[cur.r][cur.c] == map[np.r][np.c]) { | |
| // expand & 방문 처리 | |
| push(np.r, np.c); | |
| visited[np.r][np.c] = 1; | |
| } | |
| } | |
| } | |
| int main(void) { | |
| inputData(); | |
| int cnt = 0; | |
| for (int i = 0; i < N; i++) { | |
| for (int j = 0; j < M; j++) { | |
| if (visited[i][j] != 1) { | |
| BFS(i, j); | |
| cnt++; | |
| } | |
| } | |
| } | |
| printf("%d", cnt); | |
| return 0; | |
| } |