SW Expert Academy 15612_체스판 위의 룩 배치 문제풀이 in C++

2022년 11월 08일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

SWEA : 15612_체스판 위의 룩 배치

문제 요구사항

---

• 8 x 8 크기의 체스판 위의 몇 개의 칸에 룩(rook)이 놓여 있다.
• 각 칸에는 최대 1개의 룩을 놓을 수 있으므로, 체스판 위에는 0개 이상 64개 이하의 룩이 놓여 있는 것이다.
• 이때, 현재 체스판의 배치가 다음 조건을 모두 만족하는지를 판별하는 프로그램을 작성하라.
  • 정확히 8개의 룩이 있어야 한다.
  • 모든 룩은 서로 공격할 수 없어야 한다. 즉, 서로 다른 두 룩은 같은 열에 있거나 같은 행에 있으면 안 된다.

[입력]

• 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
• 각 테스트 케이스는 여덟 개의 줄로 이루어지며, 각 줄에는 길이가 8인 ‘O’ 또는 ‘.’로 구성된 문자열이 주어진다.
• i번째 줄의 j번째 글자는, 체스판의 i행 j열에 룩이 하나 놓여 있다면 ‘O’, 아무것도 놓여 있지 않다면 ‘.’이다.

[출력]

• 각 테스트 케이스마다, 주어진 체스판의 배치가 주어진 모든 조건을 만족한다면 ‘yes’를, 하나라도 만족하지 않는다면 ‘no’를 출력한다.

접근 방법

---

• Queue를 생성해, 맵 정보를 입력 받을 때, rock ( ‘O’ )를 만나면 해당 Queue에 좌표를 넣고, Queue 사이즈가 8이 아니라면 바로 결과를 출력할 수 있게 하고, 8이라면 Queue의 각 좌표들을 DFS 탐색 수행한다.

풀이 순서

---

1. TC를 입력 받고, 해당 test_case의 맵 정보를 입력 받는다.
   • 이 때, 입력 받은 맵 정보의 값이 rock( ‘O’ ) 이라면 그 좌표를 Queue에 넣는다.
2. Queue의 사이즈가 8이라면 DFS 탐색을, 아니라면 곧바로 no를 출력하도록 한다.
3. checkRock에 false 값을 넣어 초기화 하고, DFS 탐색을 수행하며, 수행 중 rock을 발견해 checkRock 값이 true로 바꼈다면, 곧바로 종료한다.
4. 이와 같은 작업 반복 후, checkRock이 true라면 no를, 아니라면 yes를 출력한다.
5. test_case 이와 같은 작업 반복

소스코드

---

#include <iostream>
#include <queue>

using namespace std;

char map[8][8];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
bool checkRook = true;

void dfs(pair<int, int> coordi, int dir) {
	int nx = coordi.first + dx[dir];
	int ny = coordi.second + dy[dir];

	if (nx >= 0 && ny >= 0 && nx < 8 && ny < 8) {
		if (map[nx][ny] == 'O')
			checkRook = true;
		else {
			dfs({ nx, ny }, dir);
		}
	}
}

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

	int TC;
	cin >> TC;

	for (int test_case = 1; test_case <= TC; test_case++) {
		checkRook = true;
		queue<pair<int, int>> q;
		for (int row = 0; row < 8; row++) {
			for (int col = 0; col < 8; col++) {
				cin >> map[row][col];

				if (map[row][col] == 'O') {
					q.push({ row, col });
				}
			}
		}

		if (q.size() == 8) {
			checkRook = false;
			while (!q.empty()) {
				for (int i = 0; i < 4; i++) {
					dfs(q.front(), i);
				}
				q.pop();

				if (checkRook)
					break;
			}
		}

		if (checkRook)
			cout << "#" << test_case << " no\n";
		else
			cout << "#" << test_case << " yes\n";
	}

	return 0;
}

문제 풀이 결과

---