[백준] 1388번 : 바닥 장식

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 BFS 방식으로 풀었다. 모든 칸을 탐색하면서 판자 모양을 확인해 판자 개수를 누적시키고 이를 출력해야한다.

1) 각 칸에 대해 (y좌표, x좌표, 판자 모양)을 저장하는 tuple들을 저장하는 큐를 선언한다.
2) 각 칸의 방문 여부 체크하는 vector를 y_size * x_size 크기로 false를 넣어 초기화한다.
3) 첫 칸을 방문 처리하고 큐에 삽입한다.
4) 큐의 최전방 노드를 삭제하고, 이에 저장된 칸과 인접한 모든 칸을 큐에 삽입한다. 단, 해당 문제는 경로를 찾는 문제가 아니고 모든 칸을 확인만 하면 되므로 위, 아래, 왼쪽, 오른쪽을 모두 확인하지 않고 오른쪽, 아래쪽으로만 이동한다. 이동할 때는 방문한 적 없는 칸으로만 이동 가능하다.

4-1) 오른쪽으로 이동했을 때

• 이동한 칸의 모양이 -인 경우
  : 이동한 칸의 왼쪽 칸의 모양이 -이 아닌 경우에만 count 증가

• 이동한 칸의 모양이 |인 경우

  • 맨 위 행일 경우 (y == 0)
    : 무조건 count 증가

  • 맨 위 행이 아닐 경우 (y > 0)
    : 이동한 칸의 위쪽 칸의 모양이 |이 아닌 경우에만 count 증가

4-2) 아래쪽으로 이동했을 때

• 이동한 칸의 모양이 -인 경우

  • 맨 왼쪽 행일 경우 (x == 0)
    : 무조건 count 증가

  • 맨 왼쪽 행이 아닐 경우 (x > 0)
    : 이동한 칸의 왼쪽 칸의 모양이 -이 아닌 경우에만 count 증가

• 이동한 칸의 모양이 |인 경우
  : 이동한 칸의 위쪽 칸의 모양이 |이 아닌 경우에만 count 증가

5) 큐가 빌 때까지 4)를 반복하고, 마지막에 count를 출력한다.

🖥️ 풀이 코드

#include <bits/stdc++.h>

using namespace std;
typedef tuple<int, int, char> tiic;

void BFS(int y_size, int x_size, vector<tiic> arr)
{
	queue<tiic> q;	

	// 방문 여부 체크하는 visited 변수 초기화
	vector<int> set_bool(x_size, 0);
	vector<vector<int>> visited(y_size, set_bool);

	// 첫 칸 큐 삽입 및 방문 처리
	q.push(arr[0]);
	visited[0][0] = true;

	int count = 1;	// 총 판자 개수 저장하는 변수

	while(!q.empty())
	{
		int y = get<0>(q.front());
		int x = get<1>(q.front());
		char ch = get<2>(q.front());

		q.pop();

		// 오른쪽으로 이동
		if (x + 1 < x_size && !visited[y][x + 1])
		{
			visited[y][x + 1] = true;
			q.push(arr[y * x_size + x + 1]);

			char next_pattern = get<2>(arr[y * x_size + x + 1]);	// 다음 칸의 패턴

			if (next_pattern == '-')		// 이동한 칸이 '-' 모양인 경우
			{
				if (next_pattern != ch)
					count++;
			}
			else							// 이동한 칸이 '|' 모양인 경우
			{
				if (y > 0)	// 맨 위 행이 아닐 때
				{
					char next_pattern_up = get<2>(arr[(y - 1) * x_size + x + 1]);	// 다음 칸 위 칸의 패턴 
					if (next_pattern != next_pattern_up)
						count++;
				}
				else
					count++;
			}
		}

		// 아래쪽으로 이동
		if (y + 1 < y_size && !visited[y + 1][x])
		{
			visited[y + 1][x] = true;
			q.push(arr[(y + 1) * x_size + x]);

			char next_pattern = get<2>(arr[(y + 1) * x_size + x]);	// 다음 칸의 패턴

			if (next_pattern == '-')		// 이동한 칸이 '-' 모양인 경우
			{
				if (x > 0)	// 맨 왼쪽 열이 아닐 때
				{
					char next_pattern_left = get<2>(arr[(y + 1) * x_size + x - 1]);	// 다음 칸 왼쪽 칸의 패턴 
					if (next_pattern != next_pattern_left)
						count++;
				}
				else
					count++;
			}
			else							// 이동한 칸이 '|' 모양인 경우
			{
				if (next_pattern != ch)
					count++;
			}
		}
	}
	cout << count;
}

int main()
{	
	int y, x; 
	cin >> y;
	cin >> x;
	cin.ignore();

	vector<tuple<int, int, char>> arr(y * x);	// 각 칸에 대해 (y좌표, x좌표, 판자 모양) 저장

	// 바닥 모양 입력하기
	for (int i = 0; i < y; i++)
	{
		string input;
		getline(cin, input);
		
		for (int j = 0; j < x; j++)
		{
			arr[i * x + j] = tiic(i, j, input[j]);	// arr[i * x + j] : 2차원 배열에서 y 좌표가 i이고 x 좌표가 j일 때, 모든 칸을 1차원 배열로 만들었을 경우의 인덱스
		}											// 한 행의 길이가 x 이므로, y가 i일 때 i * x를 해주어야 함! (i * y 아니다!)
	}
	BFS(y, x, arr);
}