[2021 카카오 채용연계형 인턴십] 거리두기 확인하기 (C++ 풀이)

https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

 

#include <string>
#include <vector>
#include <cstring>

using namespace std;

string rooms[6][6];
bool visit[6][6];
int dc[]={1,-1,0,0};
int dr[]={0,0,1,-1};
bool chkAns;

void dfs(int c, int r, int cnt, bool chkMan) {
    if(cnt==2 || chkMan==true) {
        if(chkAns==true) {
            chkAns=!chkMan;
        }

        return;
    }

    for(int i=0;i<4;i++) {
        int nc=c+dc[i];
        int nr=r+dr[i];
        bool chk=false;

        if(nc>=5 || nc<0 || nr>=5 || nr<0) {
            continue;
        }

        if(rooms[nc][nr]!="X" && visit[nc][nr]==false) {
            if(rooms[nc][nr]=="P" || chkMan) {
                chk=true;
            }
            visit[nc][nr]=true;
            dfs(nc,nr,cnt+1,chk);
            visit[nc][nr]=false;
        }
    }
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;

    for(int tc=0;tc<5;tc++) {
        memset(rooms,0,sizeof(rooms));
        memset(visit,0,sizeof(visit));
        chkAns=true;
        
        for(int i=0;i<5;i++) {
            for(int j=0;j<5;j++)
            rooms[i][j]=places[tc][i][j];
        }

        for(int i=0;i<5;i++) {
            for(int j=0;j<5;j++) {
                if(rooms[i][j]=="P") {
                    visit[i][j]=true;
                    dfs(i,j,0,false);
                    visit[i][j]=false;
                }

                if(chkAns==0) {
                    break;
                }
            }

            if(chkAns==0) {
                break;
            }
        }

        answer.push_back(chkAns);
    }

    return answer;
}

[2021 카카오 채용연계형 인턴십] 거리두기 확인하기  (C++ 풀이)

 

해결책

1. places의 각 'P'(응시자 앉은 자리) 자리마다 DFS 순회를 시작한다.

2. 조건에 부합하면 다음 자리로 이동한다. 이 때, visit[][] 배열을 이용하여 중복 탐색을 방지한다. (Time Limit 실패 대비)

3. 테이블은 지나다닐 수 있는 자리로 간주하고 탐색하여, 2칸 안에 다른 응시자를 발견하면 해당 케이스의 결과는 0이다. 물론 단 한 번의 경우도 그렇지 않다면 1이 되겠다.

4. 이렇게 총 5번의 케이스의 좌표에 대해 1~3번의 로직을 처리한다.

 

필자의 잡설

맨 처음 문제를 봤을 때는 다중 loop로 풀어야겠다고 생각했다.

그게 출제자 의도 같기도 했고..

단순한 브루트 포스 방식이기 때문에

가장 먼저 검토해보는 해결책 후보 1순위이다.

 

그러다 다른 방식으로 풀고 싶어서

그리고 코드 길이를 최소한으로 짜고 싶어서..

속 편한 재귀, 즉 DFS로 완전 탐색을 돌려버렸다. (채점서버야.. 미안해..)