삼성 코딩테스트 준비하면서 푼 문제이다.
다른사람들은 다들 코드를 짧게 효율적으로 잘짜던데 나는 왜 안될까....
그래도 맞긴 맞았다.
dfs로 풀었는데, 트리구조에서 모든 노드 탐색하고 최소값 갱신해주는 형태로 풀었다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct pos {
int x;
int y;
};
int board[8][8];
int N, M;
int min_cnt = 100;
void count_zero(int p_board[8][8]) {
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (p_board[i][j] == 0)cnt++;
}
}
if (min_cnt > cnt)min_cnt = cnt;
}
void dfs(int p_board[8][8], vector<pos> vec1, vector<pos> vec2, vector<pos> vec3, vector<pos> vec4, vector<pos> vec5) {
int c_board[8][8];
while (!vec5.empty()) {
pos cur = vec5.back();
vec5.pop_back();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
c_board[i][j] = p_board[i][j];
}
}
for (int i = cur.x; i < N; i++) {
if (c_board[i][cur.y] == 6) break;
else {
c_board[i][cur.y] = 7;
}
}
for (int i = cur.x; i >= 0; i--) {
if (c_board[i][cur.y] == 6) break;
else {
c_board[i][cur.y] = 7;
}
}
for (int i = cur.y; i < M; i++) {
if (c_board[cur.x][i] == 6)break;
else {
c_board[cur.x][i] = 7;
}
}
for (int i = cur.y; i >= 0; i--) {
if (c_board[cur.x][i] == 6)break;
else {
c_board[cur.x][i] = 7;
}
}
dfs(c_board,vec1,vec2,vec3,vec4,vec5);
}
while (!vec4.empty()) {
pos cur = vec4.back();
vec4.pop_back();
for (int a = 0; a < 4; a++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
c_board[i][j] = p_board[i][j];
}
}
if (a == 0) {
for (int i = cur.x; i >= 0; i--) {
if (c_board[i][cur.y] == 6)break;
c_board[i][cur.y] = 7;
}
for (int i = cur.x; i < N; i++) {
if (c_board[i][cur.y] == 6)break;
c_board[i][cur.y] = 7;
}
for (int i = cur.y; i >= 0; i--) {
if (c_board[cur.x][i] == 6)break;
c_board[cur.x][i] = 7;
}
}
else if (a == 1) {
for (int i = cur.x; i >= 0; i--) {
if (c_board[i][cur.y] == 6)break;
c_board[i][cur.y] = 7;
}
for (int i = cur.x; i < N; i++) {
if (c_board[i][cur.y] == 6)break;
c_board[i][cur.y] = 7;
}
for (int i = cur.y; i < M; i++) {
if (c_board[cur.x][i] == 6)break;
c_board[cur.x][i] = 7;
}
}
else if (a == 2) {
for (int i = cur.x; i < N; i++) {
if (c_board[i][cur.y] == 6)break;
c_board[i][cur.y] = 7;
}
for (int i = cur.y; i < M; i++) {
if (c_board[cur.x][i] == 6)break;
c_board[cur.x][i] = 7;
}
for (int i = cur.y; i >= 0; i--) {
if (c_board[cur.x][i] == 6)break;
c_board[cur.x][i] = 7;
}
}
else if (a == 3) {
for (int i = cur.x; i >= 0; i--) {
if (c_board[i][cur.y] == 6)break;
c_board[i][cur.y] = 7;
}
for (int i = cur.y; i < M; i++) {
if (c_board[cur.x][i] == 6)break;
c_board[cur.x][i] = 7;
}
for (int i = cur.y; i >= 0; i--) {
if (c_board[cur.x][i] == 6)break;
c_board[cur.x][i] = 7;
}
}
dfs(c_board, vec1, vec2, vec3, vec4, vec5);
}
}
while (!vec3.empty()) {
pos cur = vec3.back();
vec3.pop_back();
for (int a = 0; a < 4; a++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
c_board[i][j] = p_board[i][j];
}
}
if (a == 0) {
for (int i = cur.x; i < N; i++) {
if (c_board[i][cur.y] == 6)break;
c_board[i][cur.y] = 7;
}
for (int i = cur.y; i < M; i++) {
if (c_board[cur.x][i] == 6)break;
c_board[cur.x][i] = 7;
}
}
else if (a == 1) {
for (int i = cur.x; i >=0; i--) {
if (c_board[i][cur.y] == 6)break;
c_board[i][cur.y] = 7;
}
for (int i = cur.y; i < M; i++) {
if (c_board[cur.x][i] == 6)break;
c_board[cur.x][i] = 7;
}
}
else if (a == 2) {
for (int i = cur.x; i < N; i++) {
if (c_board[i][cur.y] == 6)break;
c_board[i][cur.y] = 7;
}
for (int i = cur.y; i >=0; i--) {
if (c_board[cur.x][i] == 6)break;
c_board[cur.x][i] = 7;
}
}
else if (a == 3) {
for (int i = cur.x; i >= 0; i--) {
if (c_board[i][cur.y] == 6)break;
c_board[i][cur.y] = 7;
}
for (int i = cur.y; i >= 0; i--) {
if (c_board[cur.x][i] == 6)break;
c_board[cur.x][i] = 7;
}
}
dfs(c_board, vec1, vec2, vec3, vec4, vec5);
}
}
while (!vec2.empty()) {
pos cur = vec2.back();
vec2.pop_back();
for (int a = 0; a < 2; a++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
c_board[i][j] = p_board[i][j];
}
}
if (a == 0) {
for (int i = cur.x; i < N; i++) {
if (c_board[i][cur.y] == 6)break;
else {
c_board[i][cur.y] = 7;
}
}
for (int i = cur.x; i >=0; i--) {
if (c_board[i][cur.y] == 6)break;
else {
c_board[i][cur.y] = 7;
}
}
}
else if (a == 1) {
for (int i = cur.y; i < M; i++) {
if (c_board[cur.x][i] == 6)break;
else {
c_board[cur.x][i] = 7;
}
}
for (int i = cur.y; i >= 0; i--) {
if (c_board[cur.x][i] == 6)break;
else {
c_board[cur.x][i] = 7;
}
}
}
dfs(c_board, vec1, vec2, vec3, vec4, vec5);
}
}
while (!vec1.empty()) {
pos cur = vec1.back();
vec1.pop_back();
for (int a = 0; a < 4; a++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
c_board[i][j] = p_board[i][j];
}
}
if (a == 0) {
for (int j = cur.x; j < N; j = j + 1) {
if (c_board[j][cur.y] == 6)break;
else {
c_board[j][cur.y] = 7;
}
}
}
else if (a == 2) {
for (int j = cur.x; j >= 0; j = j - 1) {
if (c_board[j][cur.y] == 6)break;
else {
c_board[j][cur.y] = 7;
}
}
}
else if (a == 3) {
for (int j = cur.y; j < M; j++) {
if (c_board[cur.x][j] == 6)break;
else {
c_board[cur.x][j] = 7;
}
}
}
else {
for (int j = cur.y; j >= 0; j--) {
if (c_board[cur.x][j] == 6)break;
else {
c_board[cur.x][j] = 7;
}
}
}
dfs(c_board,vec1,vec2,vec3,vec4,vec5);
}
}
count_zero(p_board);
}
int main() {
vector<pos> vec1, vec2, vec3, vec4, vec5;
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> board[i][j];
if (board[i][j] == 1) {
vec1.push_back({ i,j,0 });
}
else if (board[i][j] == 2) {
vec2.push_back({ i,j });
}
else if (board[i][j] == 3) {
vec3.push_back({ i,j });
}
else if (board[i][j] == 4) {
vec4.push_back({ i,j });
}
else if (board[i][j] == 5) {
vec5.push_back({ i,j });
}
}
}
dfs(board,vec1,vec2,vec3,vec4,vec5);
cout << min_cnt << endl;
}
