[프로그래머스/C++] 혼자서 하는 틱택토

문제

https://school.programmers.co.kr/learn/courses/30/lessons/160585

프로그래머스

 

 

---

 

코드

#include <string>
#include <vector>
#include <map>

using namespace std;

int dr[] = {1,0,1,1};
int dc[] = {0,1,1,-1};

int dfs(int r, int c, int depth, vector<string> board, char ch, int idx)
{
    if(depth==3)
        return 1;
    if(board[r][c]==ch){
        return dfs(r+dr[idx], c+dc[idx], depth+1, board, ch, idx);
    }
    else return 0;
}

int solution(vector<string> board) {
    int answer = 1;
    map<char, int> cnt_m;
    cnt_m.insert({'O', 0});
    cnt_m.insert({'X', 0});
    map<char, int> win_m;
    win_m.insert({'O', 0});
    win_m.insert({'X', 0});
    
    for(int i=0;i<board.size();i++)
    {
        for(int j=0;j<board[i].size();j++){ 
            char ch = board[i][j];
            if(ch=='.') continue;
            if(i==0&&j==0){
                win_m[ch]+=dfs(i, j, 0, board, ch, 2);
            }
            if(i==0&&j==2)
            {
                win_m[ch]+=dfs(i, j, 0, board, ch, 3);
            }
            if(i==0){
                win_m[ch]+=dfs(i, j, 0, board, ch, 0);
            }
            if(j==0)
            {
                win_m[ch]+=dfs(i, j, 0, board, ch, 1);
            }
            cnt_m[ch]++;
        }
    }
    int cnt_o = cnt_m['O'];
    int cnt_x = cnt_m['X'];
    int win_o = win_m['O'];
    int win_x = win_m['X'];
    if(cnt_o<cnt_x||cnt_o>cnt_x+1||win_o>1||win_x>1||(win_o>0&&(cnt_o==cnt_x))||(win_x>0&&(cnt_o>cnt_x))){
        answer = 0;
    }
    if(cnt_o==5&&cnt_x==4&&win_x==0)
        answer = 1;
    return answer;
}

 

---

 

풀이

경우의 수를 구하는 게 어려웠다...

예상치 못한 경우가 있어서 한참을 헤맸다...

(구조 짜는데도 어려움이 좀 있었던 것이 처음부터 dfs 시도하려고는 했다만 멍때리고 쭉 써내려갔다간 코드가 더러워질 것 같았던..ㅎ)

순회할 때 나 같은 경우 r = 0 인 부분과 c = 0인 부분에서 일정 방향으로 탐색하여 문자가 3번 반복일 경우 이긴 횟수를 증가하는 방향으로 구현하였다.

그냥 글자 갯수는 for문에서 체크하면서 더했음.

이건 그냥저냥 했고, 옳은 게임인지 아닌지를 판별할 때 힘들었다..

 

처음 생각했던 게임을 잘못한 경우들

1. X의 갯수가 O의 갯수보다 많은 경우

2. O의 갯수가 X의 갯수보다 2개 이상 많은 경우

3. O가 이긴 경우의 수가 2번 이상인 경우

4. X가 이긴 경우의 수가 2번 이상인 경우

5. O와 X가 동시에 이긴 경우

 

이정도로만 생각했더니

ㅎ....

몇 번 케이스가 틀렸는지 보여주지도 못할 정도로 많이 틀렸다...

 

사실 이 이후는 힌트만 냅다 파헤쳤다...ㅎ

 

해답을 얻은 뒤 두번째로 생각했던 경우들

1. 첫번째 생각했던 경우들

2. O가 이겼지만 O와 X의 갯수가 같은 경우

3. X가 이겼지만 O가 X보다 1개 더 많은 경우

 

결과를 보니

아까보단 낫더라

6,12,23,28,30,33,42번이 틀렸다...

그 뒤로 다시 또 냅다 힌트 파헤치기...

 

 

그렇게 해서 얻은 마지막 경우

O가 이긴 갯수가 2개가 나와도 옳은 결과일 수도 있더라...

교차점에 O를 놓음으로써 동시에 2개가 나올수도 있던 것...

 

O	O	O
O	X	X
O	X	X

 

요런 상황도 있다는 걸 몰랐었던 1인

그리고 이런 상황이 되기 위해서는 다음과 같은 조건이 필요하였다.

1. O의 개수가 5, X의 개수가 4이어야만 한다.

2. X가 이긴 경우가 없어야 한다.

 

 

그래서 마지막에 다음 조건을 추가하였고 결과는 통과!

 

---

 

사실 이것도 오래 걸리면 안되는 문제인데도 오래 걸렸어서(시간 단위로 걸려버림...ㄹㅈㄷ) 슬픔이 이만저만이 아니다..

심지어 다른 사람들이 올려놓은 힌트마저 참고해버렸으니... 언제쯤 다시 실력이 늘까...?