[SWEA] 삼복치 C++

in Study on Coding Test


문제링크_로그인필요

최초로 내 힘으로 푼 BFS문제 그리고 삽질끝에 풀어서 기억에 남는 문제.
포스트로 한번 남겨보았음.

정답제출코드


#include <stdio.h>
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int n = 0, m = 0;

int int_map[101][101] = {0};

int visited_bed[101][101] = {0};
int visited_chair[101][101] = {0};
int visited_bottom[101][101] = {0};

queue<pair<int, int>> q; // 탐색 좌표 저장에 사용할 큐

int* bed_chair_bottom[3];

int bed_bok[2] = {0, 0};
int chair_bok[2] = {0, 0};
int bottom_bok[2] = {0, 0};

// 침대, 의자, 바닥의 좌표 저장
int bed[2] = {0, 0};
int chair[2] = {0, 0};
int bottom[2] = {0, 0};


void bfs_bed(int x, int y)
{
    // bfs의 기본 구조
    visited_bed[x][y] = 1;
    
    q.push(make_pair(x, y)); // 큐에 삽입

    while (!q.empty()) // 큐가 비어있지 않은 동안 -> 모든 좌표를 탐색할 동안
    {
        // 큐의 맨 앞좌표를 현재 좌표로 지정
        x = q.front().first;
        y = q.front().second;

        // 큐의 맨 앞 좌표 제거 (방문했으니 제거!)
        q.pop();
        
        // 상하좌우 인접한 좌표를 확인하는 곳.
        for (int i = 0; i < 4; i++)
        {
            // 상하좌우로 인접한 좌표
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 인접한 좌표가 미로에 있는지, 방문했는지, 이동이 가능한지 확인.
            if (visited_bed[nx][ny] == 0 && int_map[nx][ny] != 0 && (!(nx < 0 || nx >= n || ny < 0 || ny >= m)))
            {
                q.push(make_pair(nx, ny)); // 조건에 맞는 인접 좌표를 queue에 삽입.
                visited_bed[nx][ny] = visited_bed[x][y] + 1; // 조건에 맞는 인접 좌표에 거리 기록
            }
        }
    }

    return;
}

void bfs_chair(int x, int y)
{
    // bfs의 기본 구조
    visited_chair[x][y] = 1;
    
    q.push(make_pair(x, y)); // 큐에 삽입

    while (!q.empty()) // 큐가 비어있지 않은 동안 -> 모든 좌표를 탐색할 동안
    {
        // 큐의 맨 앞좌표를 현재 좌표로 지정
        x = q.front().first;
        y = q.front().second;

        // 큐의 맨 앞 좌표 제거 (방문했으니 제거!)
        q.pop();
        
        // 상하좌우 인접한 좌표를 확인하는 곳.
        for (int i = 0; i < 4; i++)
        {
            // 상하좌우로 인접한 좌표
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 인접한 좌표가 미로에 있는지, 방문했는지, 이동이 가능한지 확인.
            if (visited_chair[nx][ny] == 0 && int_map[nx][ny] != 0 && (!(nx < 0 || nx >= n || ny < 0 || ny >= m)))
            {
                q.push(make_pair(nx, ny)); // 조건에 맞는 인접 좌표를 queue에 삽입.
                visited_chair[nx][ny] = visited_chair[x][y] + 1; // 조건에 맞는 인접 좌표에 거리 기록
            }
        }
    }

    return;
}

void bfs_bottom(int x, int y)
{
    // bfs의 기본 구조
    visited_bottom[x][y] = 1;
    
    q.push(make_pair(x, y)); // 큐에 삽입

    while (!q.empty()) // 큐가 비어있지 않은 동안 -> 모든 좌표를 탐색할 동안
    {
        // 큐의 맨 앞좌표를 현재 좌표로 지정
        x = q.front().first;
        y = q.front().second;

        // 큐의 맨 앞 좌표 제거 (방문했으니 제거!)
        q.pop();
        
        // 상하좌우 인접한 좌표를 확인하는 곳.
        for (int i = 0; i < 4; i++)
        {
            // 상하좌우로 인접한 좌표
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 인접한 좌표가 미로에 있는지, 방문했는지, 이동이 가능한지 확인.
            if (visited_bottom[nx][ny] == 0 && int_map[nx][ny] != 0 && (!(nx < 0 || nx >= n || ny < 0 || ny >= m)))
            {
                q.push(make_pair(nx, ny)); // 조건에 맞는 인접 좌표를 queue에 삽입.
                visited_bottom[nx][ny] = visited_bottom[x][y] + 1; // 조건에 맞는 인접 좌표에 거리 기록
            }
        }
    }

    return;
}

int get_distance(int a, int b, int c, int distance_min)
{
    int distance = 0;

    // 각각 bed복치, chair복치, bottom복치 입장에서 각 목적지 까지 거리 구하기.
    int distance1 = visited_bed[bed_chair_bottom[a][0]][bed_chair_bottom[a][1]] - 1;
    int distance2 = visited_chair[bed_chair_bottom[b][0]][bed_chair_bottom[b][1]] - 1;
    int distance3 = visited_bottom[bed_chair_bottom[c][0]][bed_chair_bottom[c][1]] - 1;

    distance = distance1 + distance2 + distance3;

    // 하나라도 -1이면 무효로 처리해야함.
    if (distance1 != -1 && distance2 != -1 && distance3 != -1)
    {
        // 이 조건문에 들어왔다는 것은 경로가 유효하다는 이야기.
        if (distance_min > distance || distance_min == -1)
            distance_min = distance;
    }

    else
    {
        return -1;
    }

    return distance_min;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int test_case = 0;
    scanf("%d", &test_case);

    for (int i = 0; i < test_case; ++i)
    {
        // 맵 초기화
        memset(int_map, 0, sizeof(int_map));

        memset(visited_bed, 0, sizeof(visited_bed));
        memset(visited_chair, 0, sizeof(visited_chair));
        memset(visited_bottom, 0, sizeof(visited_bottom));

        cin >> n >> m;
        //scanf("%d %d", &n, &m);

        for (int j = 0; j < n; ++j)
        {

            // 이상하게 string으로 저장하면 탐색과정에서 오류남.
            // 그래서 숫자로 저장해두기 위한 장치.
            for (int k = 0; k < m; ++k)
            {
                char s;
                
                cin >> s;

                if (s == '.')
                    int_map[j][k] = 1;

                else if (s == 'B')
                {
                    int_map[j][k] = 1;
                    bed[0] = j;
                    bed[1] = k;
                }

                else if (s == 'C')
                {
                    int_map[j][k] = 1;
                    chair[0] = j;
                    chair[1] = k;
                }

                else if (s == '_')
                {
                    int_map[j][k] = 1;
                    bottom[0] = j;
                    bottom[1] = k;
                }

                else if (s == '#')
                    int_map[j][k] = 0;

            }
        }

        bed_chair_bottom[0] = bed;
        bed_chair_bottom[1] = chair;
        bed_chair_bottom[2] = bottom;

        // 각 복치들의 좌표 저장
        int x, y;
        cin >> x >> y;

        bed_bok[0] = x - 1;
        bed_bok[1] = y - 1;

        cin >> x >> y;

        chair_bok[0] = x - 1;
        chair_bok[1] = y - 1;

        cin >> x >> y;

        bottom_bok[0] = x - 1;
        bottom_bok[1] = y - 1;

        int distance_min = 10000; // 임의의 큰수

        // bfs로  거리맵 형성

        bfs_bed(bed_bok[0], bed_bok[1]);
        bfs_chair(chair_bok[0], chair_bok[1]);
        bfs_bottom(bottom_bok[0], bottom_bok[1]);


        // 경우의수 6가지

        distance_min = get_distance(0, 1, 2, distance_min);
        distance_min = get_distance(0, 2, 1, distance_min);
        distance_min = get_distance(1, 0, 2, distance_min);
        distance_min = get_distance(1, 2, 0, distance_min);
        distance_min = get_distance(2, 0, 1, distance_min);
        distance_min = get_distance(2, 1, 0, distance_min);
        
        printf("#%d %d\n", i+1, distance_min);
    }

    return 0;
}


소스코드 설명


  • 지도 탐색으로는 BFS 알고리즘을 사용하였음.

  • 개복치들, 침대, 의자, 바닥의 좌표를 길이가 2인 ArrayList에 저장하고, 가구들은 경우의 수를 원활하게 비교하기 위해서 벡터에다가 좌표를 저장하였음.
    즉, ((침대좌표),(바닥좌표),(의자좌표))와 같은 상태임.

  • 3개의 맵을 형성하였고, (visited_bed, visited_bottom, visited_chair)
    각기 다른 맵에 기록하기 위해서 비효율적이지만 같은 bfs 함수를 각각 3개 사용하였음.
    (맵을 하나의 벡터에 저장하고 싶었지만 구현에 어려움이 커서 같은 bfs함수를 3개 사용하는 방법을 썼음.)

  • 시간초과가 많이 떠서 구동 속도를 높이기 위해서 map에는 ArrayList를 사용함.

  • 3개의 가구를 옮기는 경우의 수는 총 6개이므로 get_distance 함수를 6번 호출하였음.


삽질한 내용


아래는 내가 삽질했던 코드이다.

#include <iostream>
#include <queue>
#include <string>
#include <vector>
 
using namespace std;
 
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
 
int n = 0, m = 0;
 
int int_map[100][100];
 
queue<pair<int, int>> q; // 탐색 좌표 저장에 사용할 큐
 
vector<int> bed_chair_bottom[3];
 
int bed_bok[2] = {0, 0};
int chair_bok[2] = {0, 0};
int bottom_bok[2] = {0, 0};
 
 
int bfs(int x, int y, int target_x, int target_y)
{
    int visited[100][100] = {0}; // 방문여부
    // bfs의 기본 구조
    visited[x][y] = 1;
     
    q.push(make_pair(x, y)); // 큐에 삽입
 
    while (!q.empty()) // 큐가 비어있지 않은 동안 -> 모든 좌표를 탐색할 동안
    {
        // 큐의 맨 앞좌표를 현재 좌표로 지정
        x = q.front().first;
        y = q.front().second;
 
        // 큐의 맨 앞 좌표 제거 (방문했으니 제거!)
        q.pop();
         
        // 상하좌우 인접한 좌표를 확인하는 곳.
        for (int i = 0; i < 4; i++)
        {
            // 상하좌우로 인접한 좌표
            int nx = x + dx[i];
            int ny = y + dy[i];
             
            // 인접한 좌표가 미로에 있는지, 방문했는지, 이동이 가능한지 확인.
            if (visited[nx][ny] == 0 && int_map[nx][ny] != 0 && (!(nx < 0 || nx >= n || ny < 0 || ny >= m)))
            {
                q.push(make_pair(nx, ny)); // 조건에 맞는 인접 좌표를 queue에 삽입.
                visited[nx][ny] = visited[x][y] + 1; // 조건에 맞는 인접 좌표에 거리 기록
            }
        }
    }
 
    return visited[target_x][target_y] - 1;
}
 
int get_distance(int a, int b, int c, int distance_min)
{
    int distance = 0;
 
    int distance1 = bfs(bed_bok[0], bed_bok[1], bed_chair_bottom[a][0], bed_chair_bottom[a][1]);
    int distance2 = bfs(chair_bok[0], chair_bok[1], bed_chair_bottom[b][0], bed_chair_bottom[b][1]);
    int distance3 = bfs(bottom_bok[0], bottom_bok[1], bed_chair_bottom[c][0], bed_chair_bottom[c][1]);
 
    distance = distance1 + distance2 + distance3;
 
    // 하나라도 -1이면 무효로 처리해야함.
    if (distance1 != -1 && distance2 != -1 && distance3 != -1)
    {
        // 이 조건문에 들어왔다는 것은 경로가 유효하다는 이야기.
        if (distance_min > distance || distance_min == -1)
            distance_min = distance;
    }
 
    else
    {
        distance_min = -1;
    }
 
    return distance_min;
}
 
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int test_case = 0;
    cin >> test_case;
 
    for (int i = 0; i < test_case; ++i)
    {
        cin >> n >> m;
 
        // 침대, 의자, 바닥의 좌표 저장
        vector<int> bed = {0, 0};
        vector<int> chair = {0, 0};
        vector<int> bottom = {0, 0};
 
        for (int j = 0; j < n; ++j)
        {
            string s;
            cin >> s;
 
            // 이상하게 string으로 저장하면 탐색과정에서 오류남.
            // 그래서 숫자로 저장해두기 위한 장치.
            for (int k = 0; k < s.length(); ++k)
            {
                if (s[k] == '.')
                    int_map[j][k] = 1;
 
                else if (s[k] == 'B')
                {
                    int_map[j][k] = 2;
                    bed[0] = j;
                    bed[1] = k;
                }
 
                else if (s[k] == 'C')
                {
                    int_map[j][k] = 3;
                    chair[0] = j;
                    chair[1] = k;
                }
 
 
                else if (s[k] == '_')
                {
                    int_map[j][k] = 4;
                    bottom[0] = j;
                    bottom[1] = k;
                }
 
 
                else if (s[k] == '#')
                    int_map[j][k] = 0;
            }
 
        }
 
        bed_chair_bottom[0] = bed;
        bed_chair_bottom[1] = chair;
        bed_chair_bottom[2] = bottom;
 
        // 각 복치들의 좌표 저장
        int x, y;
        cin >> x >> y;
 
        bed_bok[0] = x - 1;
        bed_bok[1] = y - 1;
 
        cin >> x >> y;
 
        chair_bok[0] = x - 1;
        chair_bok[1] = y - 1;
 
        cin >> x >> y;
 
        bottom_bok[0] = x - 1;
        bottom_bok[1] = y - 1;
 
        int distance_min = 10000; // 임의의 큰수
 
        distance_min = get_distance(0, 1, 2, distance_min);
        distance_min = get_distance(0, 2, 1, distance_min);
        distance_min = get_distance(1, 0, 2, distance_min);
        distance_min = get_distance(1, 2, 0, distance_min);
        distance_min = get_distance(2, 0, 1, distance_min);
        distance_min = get_distance(2, 1, 0, distance_min);
 
        cout << '#' << i + 1 << ' ' << distance_min << endl;
 
    }
     
    return 0;
}

요약을 하자면 정답 코드와 결정적 차이는

get_distance 함수에서 bfs함수를 3번 씩이나 호출해서 시간을 지연시켰다는 점이다.

그리고 본문에서 get_distance함수는 6번이나 호출되니 총 BFS함수를 18번씩이나 호출한 것이다.

당연히 시간이 지연될 수 밖에 없었다.

그래서 내가 고민한 점은 BFS 함수의 호출 횟수를 최대한 줄이는 것이었다.

거리를 구할 때마다 bfs함수를 호출해서 거리를 구하는 것이 아니라,

어차피 출발지점은 똑같으니까 bfs함수를 한번만 호출해서 출발지점으로부터의 거리를 맵에다 그린 다음에

거리를 구하는 함수에서 맵에서 출발 지점으로부터의 추출하는 방법을 생각했다.

다시 한번 말하지만 바닥, 의자, 침대의 위치는 바뀌어도 개복치의 위치는 바뀌지 않는다.

즉, 출발지점은 똑같기 때문에 그냥 각기 개복치에 해당하는 visited에서 목표지점까지의 거리를 뽑아오면 되는 것이다.

  • 침대 복치의 지점별 이동거리 : visited_bed
  • 의자 복치의 지점별 이동거리 : visited_chair
  • 바닥 복치의 지점별 이동거리 : visited_bottom

이렇게 해서 테스트케이스 별로 bfs함수 호출 횟수를 18회에서 3회로 줄였다.

그래서 1초가 넘어가는 구동시간을 287ms로 줄일 수 있었다.


또 다른 삽질 내용으로는 새로운 테스트 케이스를 위해서 map을 초기화 해주어야 했다.

// 맵 초기화
memset(int_map, 0, sizeof(int_map));

memset(visited_bed, 0, sizeof(visited_bed));
memset(visited_chair, 0, sizeof(visited_chair));
memset(visited_bottom, 0, sizeof(visited_bottom));

정답 코드에는 위와 같이 memset함수를 사용해주어야 한다. memset함수는 string 헤더에 있다.

원래 코드는 아래와 같았다.

int_map[101][101] = {0};
visited_bed[101][101] = {0};
visited_chair[101][101] = {0};
visited_bottom[101][101] = {0};

이렇게 단순히 0으로 초기화 시킨다고 초기화가 되지 않더라..

차지하는 메모리의 위치가 달라서 그런가 생각이 든다.

memset 함수를 이용하면 같은 지점에 있는 메모리를 새로 초기화 할 수 있기 때문에 배열을 초기화할 땐 memset을 이용해야한다는 것을 알았다.

ios_base::sync_with_stdio(false);
    cin.tie(NULL);

그리고 또 다른 내용으로는 C++로 테스트를 볼 때에는 위의 코드를 main함수 맨 처음에 써주어야 시간초과가 뜨지 않는 경우도 있다는 것을 알았다.

© 2022.07. by Wookey_Kim

Powered by Hydejack v7.5.2