[백준OJ] 9079번 동전 게임

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

9079번: 동전 게임

---

 

풀이

BFS알고리즘을 이용하여 문제를 해결했다. BFS를 이용할때, 이전에 만났던 동전들의 상태를 체크해주기위해, 먼저 입력받은 동전들을 H는1로, T는 0으로 초기화를 시켜준 뒤, 해당 배열을 이진수로 나타내어 해당 상태를 체크해주었다.

예시 1번을 예를들어 설명해보자면, 처음 입력했을때 다음과 같이 초기화를 해준다.

H T T		1 0 0
H T T  => 	1 0 0 
T H H		0 1 1

 

그런뒤, 현재 상태를 2진수로 표현하였다.

1 0 0
1 0 0  = > 1 0 0 1 0 0 0 1 1 => 291
0 1 1

해당 상태를 291로 매핑을 시켜준 뒤, 291은 방문을 했다는 표시를 해주고 처음 queue에 넣어준다.

 

그런뒤, 모든행,모든열, 모든 대각선을 바꿔주며 BFS를 실행하면된다.

 

시간복잡도

행, 열, 대각선을 바꾸는 알고리즘은 모두 O(1)

현재 상태를 정수로 매핑하는 알고리즘또한 O(1)

현재 매핑된 정수를 가지고 maze를 표현하는 알고리즘 O(1)

BFS는 최대 512번( 000000000~111111111)돌기때문에, O(1)

따라서 O(T) 시간이 걸린다.

 

반응형

코드

#include <iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAX 987654321
using namespace std;

int maze[3][3];
int t,result;
bool visited[512];

//열 바꾸는 함수
void col_change(int col) {
	for (int i = 0; i < 3; i++) {
		maze[i][col] = (maze[i][col] == 1 ? 0 : 1);
	}
}

//행 바꾸는 함수
void row_change(int row) {
	for (int i = 0; i < 3; i++) {
		maze[row][i] = (maze[row][i] ==1 ? 0 : 1);
	}
}

//대각선 바꾸는 함수
void cross_change(int dir) {
	for (int i = 0; i < 3; i++) {
		if (dir == 0) {
			maze[i][i] = (maze[i][i] == 1 ? 0 : 1);
		}
		else {
			maze[i][2 - i] = (maze[i][2 - i] == 1 ? 0 : 1);
		}
	}
}

//모든면이 같은지 확인하는 함수
bool isCorrect() {
	char temp = maze[0][0];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (temp != maze[i][j]) {
				return false;
			}
		}
	}
	return true;
}

//현재 상태를 정수로 매핑하는 함수
int maze_to_int() {
	int now = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			now = now * 2 + maze[i][j];
		}
	}
	return now;
}

//매핑된 함수를 이용하여 현재 상태를 표현해주는 함수
void int_to_maze(int number) {
	for (int i = 2; i >=0; i--) {
		for (int j = 2; j >=0; j--) {
			maze[i][j] = number % 2;
			number /= 2;
		}
	}
}

int bfs() {
	queue<pair<int, int>> q;
	int first = maze_to_int();
	q.push({ first,0 });
	visited[first] = true;

	while (!q.empty()) {
		int now = q.front().first;
		int cnt = q.front().second;
		q.pop();

		int_to_maze(now);

		if (isCorrect()) {
			return cnt;
		}

		//열 변환
		for (int i = 0; i < 3; i++) {
			col_change(i);
			int next = maze_to_int();
			if (!visited[next]) {
				visited[next] = true;
				q.push({ next ,cnt + 1 });
			}
			col_change(i);
		}

		//행변환
		for (int i = 0; i < 3; i++) {
			row_change(i);
			int next = maze_to_int();
			if (!visited[next]) {
				visited[next] = true;
				q.push({ next ,cnt + 1 });
			}
			row_change(i);
		}
		//대각선 변환
		for (int i = 0; i <= 1; i++) {
			cross_change(i);
			int next = maze_to_int();
			if (!visited[next]) {
				visited[next] = true;
				q.push({ next ,cnt + 1 });
			}
			cross_change(i);
		}
	}
	return -1;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> t;
	while (t--) {
		result = MAX;
		memset(visited, false, sizeof(visited));
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				char data;
				cin >> data;
				if (data == 'H') {
					maze[i][j] = 1;
				}
				else {
					maze[i][j] = 0;
				}
			}
		}
		cout << bfs() << "\n";

		
	}

	return 0;
}