[Programmers] 2021 카카오 인턴십 2번 - 거리두기 확인하기

https://programmers.co.kr/learn/courses/30/lessons/81302?language=cpp

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

처음에 풀었을때 방향이 너무 많아서 이게 뭐지? 싶었는데.. 침착하게 생각하면 금방 할 수 있었다.

하지만 그러지 못했다.

​

접근 방법

1. 거리 1일때 순회

P 발견 시 잘못된 거리두기 0 return

2. 거리 2일때 순회

P 발견시 P?P 에서 ?가 X면 괜찮다. 따라서 사이에 낀게 X인가 확인.

X가 아니면 0 return. (나는 중점 구하듯 중간의 점을 구했지만 더 좋은 방법이 있었다)

3. 대각일때 순회

P ? 이 상황에서 ?가 둘 다 X가 아닌이상 0 return.

? P

​

위의 생각을 가지고 빠르게 구현했어야 했는데, 3가지에서 멈칫 했다.

​

1. P?P 에서 ?를 어떻게 구하지?

-> 중점 처럼 2로 나누는걸 1초만에 못 떠올림

-> 더 쉬운방법을 바킹독님 블로그에서 발견함

​

2. P ? 에서 ? 의 인덱스 어떻게 구하지?

? P

-> 눈으로 구하다가 시간이 약간 걸렸다.

그냥 종이에다가 2개 예시 들어보니까 바로 나오던데.. 주제 파악 미스로 인한 실패

i,j mx, my => [i,my] [mx,j]

​

3. ? ? 둘다 X가 아니면 return인데..

? != 'X' && ? != 'X' 이렇게 써놨다. 미쳤나보다.

!(? == 'X' && ? == 'X') 이렇게 바꿨다.

 

#include<bits/stdc++.h>
#define ROW 5
#define COL 5
using namespace std;
// +1,-1
int dx[4] = {0,0,1,-1};
int dy[4] = {-1,1,0,0};
// +2, -2 
int dx2[4] = {0,0,2,-2};
int dy2[4] = {-2,2,0,0};
// 대각
int dx3[4] = {1,1,-1,-1};
int dy3[4] = {-1,1,-1,1};

int bfs(vector<string>& v)
{
    bool visited[5][5]; 
    for(int i = 0; i < 5; i++) fill(visited[i], visited[i]+5, false);
    int mx,my;
    for(int i = 0; i < ROW; i++)
    {
        for(int j = 0; j < COL; j++)
        {
            if(v[i][j] == 'P')
            {
                for(int x = 0; x < 4; x++) // 1칸이동
                {
                    mx = i + dx[x];
                    my = j + dy[x];
                    if(mx < 0 || mx >= ROW || my < 0 || my >= COL) continue;
                    if(v[mx][my] == 'P') return 0;
                    if(!visited[mx][my] && v[mx][my] == 'O')
                    {
                        visited[mx][my] = true;
                    }
                }
                
                for(int x = 0; x < 4; x++) // 2칸이동
                {
                    mx = i + dx2[x];
                    my = j + dy2[x];
                    if(mx < 0 || mx >= ROW || my < 0 || my >= COL) continue;
                    if(v[mx][my] == 'P' && v[ (i+mx) / 2 ][ (j+my) / 2 ] != 'X') return 0; //중점
                    if(!visited[mx][my] && v[mx][my] == 'O')
                    {
                        visited[mx][my] = true;
                    }
                }
                
                for(int x = 0; x < 4; x++) // 대각이동
                {
                    mx = i + dx3[x];
                    my = j + dy3[x];
                    if(mx < 0 || mx >= ROW || my < 0 || my >= COL) continue;
                    if(v[mx][my] == 'P' && !(v[i][my] == 'X' && v[mx][j] == 'X') ) return 0;
                    if(!visited[mx][my] && v[mx][my] == 'O')
                    {
                        visited[mx][my] = true;
                    }
                }
                
            }
        }
    }
    
    return 1;
    
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    int len = places[0].size();
    
    for(int i = 0; i < len; i++)
    {
        answer.push_back(bfs(places[i]));
    }
    
    
    return answer;
}

내 코드는 긴 편이다.

​

다른 코드 보고 배운점

​

1. 길이가 2일때를 1일때 * 2로 하면 된다.

dx2,dy2를 왜 만들었는지 이해가 안간다.

dx[i] * 2, dy[i] * 2 를 하면 된다.

​

2. 1번처럼 하면, P?P에서 중점으로 구하지 않고, v[ (i+mx) / 2 ][ (j+my) / 2 ]

이녀석을 v[ i + dx[x] ][ j + dy[x] ]로 바꾸면 된다.

​

3. 사이에 낀 대각의 값 구하는 인덱스, 바로 떠올릴 수 있을 것 같다.

​

천천히 하기...

실버이상 300문제 풀고 판단하기..