[ 백준 16113 ] 시그널 (C++)

https://www.acmicpc.net/problem/16113

16113번: 시그널

 

단순 구현 문제. dfs로 약간 꼼수를 썼다. 0행만 탐색하면서 검은색 칸을 만나면 연속된 검은색 칸의 개수를 구해 경우의 수를 나눴다. 0~9 까지의 숫자는 몇 개의 칸을 칠하는지로 분류할 수 있다. 아래 그림을 참고하자.

 

5칸 → 1
7칸 → 7
9칸 → 4
11칸 → 2, 3, 5
12칸 → 0, 6, 9
13칸 → 8

 

모든 숫자는 0행부터 시작한다. 따라서 (0행, 0열)부터 (0행, 끝열)까지 검은색 칸을 만나면 연속된 검은색 칸의 개수를 구하고 위 경우의 수에 따라 알맞는 숫자를 출력하면 된다. 여기서 연속된 검은색 칸의 개수를 구할때 dfs를 쓴 것이다. dfs 코드는 여기를 참고하길 바란다. 거의 그대로 가져다 썼다. 

 

11칸, 12칸인 경우만 세부적으로 분류해주면 된다. 

 

좀 대충 그리기는 했지만 보는대로다. 현재 열을 col이라 했을때 모든 숫자의 탐색 시작점은 (0, col)로 위 그림에서 파란색 점과 일치한다. 그리고 각 숫자들이 고유하게 가지거나 가지지 않는 위치를 빨간색으로 표시했다. 따라서 아래와 같이 분류 가능하다. 

시작점 = [0][col]

11칸 → 2, 3, 5
[3][col] 이 칠해졌으면 2
[1][col] 이 칠해졌으면 5
그 외는 3

12칸 → 0, 6, 9
[1][col + 2] 이 안 칠해졌으면 6
[3][col] 이 안 칠해졌으면 9
그 외는 0

 

시그널 표시판(?)을 map이라고 했을때 모든 케이스를 분류해주는 코드는 아래와 같다. dfs는 코드는 생략한다. 

 

// 0 행 col 열만 검색
for (int col = 0; col < (n / 5); col++) {
    if (map[0][col] && !visit[0][col]) {
        int count = 0; // 검은색 칸의 개수
        dfs(0, col, count);
        if (count == 5) cout << 1;
        if (count == 7) cout << 7;
        if (count == 9) cout << 4;
        if (count == 13) cout << 8;
        if (count == 11) {
            if (map[3][col]) cout << 2;
            else if (map[1][col]) cout << 5;
            else cout << 3;
        }
        if (count == 12) {
            if (!map[1][col + 2]) cout << 6;
            else if (!map[3][col]) cout << 9;
            else cout << 0;
        }
    }
}

 

끝!! 최종 코드는 아래와 같다. 

 

#include <iostream>
using namespace std;

int map[5][20000], visit[5][20000];
int n;
int m_row[] = { 1, -1, 0, 0 };
int m_col[] = { 0, 0, 1, -1 };

void dfs(int row, int col, int& count) {
	if (visit[row][col]) // 방문했으면 리턴
		return;

	visit[row][col] = 1; // 방문처리
	count++; // # 수
	for (int i = 0; i < 4; i++) {
		int xx = row + m_row[i];
		int yy = col + m_col[i];
		if (xx >= 0 && xx < 5 && yy >= 0 && yy < (n / 5)) { // 범위 검사
			if (!visit[xx][yy] && map[xx][yy]) // 방문하지 않았고 아파트 존재하면 탐색
				dfs(xx, yy, count);
		}
	}
}

int main() {
	char c;
	cin >> n;
	
	for (int row = 0; row < 5; row++) {
		for (int col = 0; col < (n / 5); col++) {
			cin >> c;
			if(c == '#')
				map[row][col] = 1;
		}
	}

	// 0 행 col 열만 검색
	for (int col = 0; col < (n / 5); col++) {
		if (map[0][col] && !visit[0][col]) {
			int count = 0; // 검은색 칸의 개수
			dfs(0, col, count);
			if (count == 5) cout << 1;
			if (count == 7) cout << 7;
			if (count == 9) cout << 4;
			if (count == 13) cout << 8;
			if (count == 11) {
				if (map[3][col]) cout << 2;
				else if (map[1][col]) cout << 5;
				else cout << 3;
			}
			if (count == 12) {
				if (!map[1][col + 2]) cout << 6;
				else if (!map[3][col]) cout << 9;
				else cout << 0;
			}
		}
	}

	return 0;
}