2024 - 10- 16 C++ 코딩테스트 10주완성 D+46

백준 15684 문제 - 사다리 조작

 

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다.

 

인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다.

 

아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다.

 

가로선은 인접한 두 세로선을 연결해야 한다.

(단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.)

 

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

 

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다.

 

이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

 

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다.

 

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다.

 

이때, i번 세로선의 결과가 i번이 나와야 한다.

그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다.
(2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1)
b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다.
세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.
입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

 

출력

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

 

3일째 이 문제를 풀어보았으나.. 도저히 내 머리로서는 결과를 도출할 수 없다.. ㅠㅠ

 

그래서 내린 결론은 앞으로는 강의를 보고 문제유형에 대한 공부를 한뒤, 다시 비슷한 문제를 풀어보는 것으로 방향으로 바꾸어야 겠다!

 

일단 강의 실습코드부터 분석해보자!

강의실습코드

 

#include <bits/stdc++.h>

using namespace std;
const int INF = 987654321;
int n,m,h,a,b,ret = INF,visited[34][34];

bool check(){
    for(int i = 1; i <= n; i++)
    {
        int start = i;
        for(int j =0; j <= h; j++)
        {
            if(visited[j][start])start++;
            else if(visited[j][start-1])start--;
        }
        if(start != i) return false;
    }
    return true;
}

void go(int here, int cnt)
{
    if(cnt > 3 || cnt >= ret) return;
    if(check())
    {
        ret = min(ret, cnt); return;
    }
    for(int i = here; i <= h; i++)
    {
        for(int j = 1; j <n; j++)
        {
            if(visited[i][j] || visited[i][j-1] || visited[i][j]) continue;
            visited[i][j] = 1;
            go(i, cnt +1);
            visited[i][j] = 0;
        }
    }
}

int main()
{
    cin >> n >> m >> h;
    for(int i=0; i < m; i++)
    {
        cin >> a >> b;
        visited[a][b] = 1;
    }

    go(1,0);
    cout << ((ret == INF) ? -1 : ret) << "\n";
    return 0;
}

 

 

먼저 문제를 풀기전에 시간복잡도부터 계산하여본다.

 

N의 최대값은 10이고 H의 최대값은 30이므로 2차원 행렬의 최댓값은 300이다.

 

그리고 구하는 추가된 가로선의 개수는 최대3개이기때문에 

 

300 C 3 이 되게된다.

 

300 * 299 * 298 / 3 * 2 를 하게 되면 4,455,100 이 나오게 된다.

 

1억미만이므로 시간복잡도가 넘지않는다!

 

이 문제의 핵심로직은 완전탐색을 visited 배열을 이용하여서 추가해야되는 가로선의 값인 ret을 출력시키는 것이다.

 

이 코드의 작동방식을 순서대로 정리하자면 이렇다.

 

1. 가로선의 좌표를 visted 배열에 집어넣는다.

2. void go(int here,int cnt) 함수안에 매개인수를 넣어 go(1,0) 을 호출한다.

3. go 안 반복문은 매개인수 here이 현재 탐색하고 있는 가로선의 시작위치이며, 여기서부터 가로선끝까지 탐색한다.

4. 연속된 가로선은 존재하지 않으므로 현재 탐색하고 있는 위치에서 j , j -1 , j + 1 이 존재할 시 continue로 다음 탐색으로 넘어간다.

5. 안넘어갈시 가로선이 없는 것이므로 visited[i][j] 의 값을 1으로 대입하고 가로선의 개수를 추가하여 재귀함수 go(i,cnt +1) 호출

6. 해당 탐색이 끝날 경우 다른 탐색이랑 방문한 위치가 겹치면 안되므로 visited[i][j] 의 값을 0으로 다시 바꿔준다.

7. 매번 재귀함수를 호출할때마다 check 함수를 호출시킨다.

8. check 함수는 visited 배열 전부를 확인하여 시작 가로선의 위치랑 도착 가로선의 위치가 일치하는지 확인하는 함수이다.

8-1. i =1 부터 세로선의 크기까지 반복문을 돌릴때마다 start라는 정수형 변수안에 i값을 대입시켜준다.

8-2. j = 1 부터 가로선의 크기만큼 반복문을 돌리고 돌릴때마다 visited[i][start] 의 값 또는 visited[j][start-1] 이 있는지 확인하여 해당 위치에서 양쪽에 가로선이 있는지 확인한다.

8-3. 만약 있을시, start++를 하고 다음 반복문으로 넘어감으로써, 해당 가로선을 따라 이동하고, 밑으로 한칸 내려간 탐색이 된다.

8-4. 이렇게 탐색하여 start 가 i면 true면 시작위치랑 도착위치랑 동일하므로 true를 반환 아니면 false를 반환한다.

9. 만약 check 함수를 만족하면 문제의 조건을 통과한것이므로, 해당 재귀함수 go안의 cnt와 ret 을 비교하여 더 작은 수를 대입시켜준다.

10. 모든 go() 함수가 종료되고 나서, ret값이 초깃값이랑 같을 시, 문제의 조건이 만족하지 않은 것이므로 -1을 출력
다를시 조건을 만족한것이므로 ret 값을 출력시켜준다.

 

check 함수안의 start 값을 이용하여 탐색을 하는 부분에서 뒤통수를 맞은 기분이였다..

 

"사다리 타기또는 이어진 경로로 이동할때에는 이런 방식을 이용하면 되겠다.." 라는 생각이 들었습니다..

 

앞으로는 기억해두고 두고두고 써먹어야겠다!

 

---

 

백준 14620번 문제 : 꽃길

 

 

난이도

 

 

 

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

 

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

 

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

 

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다.

 

꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다.

 

어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다.

 

또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

 

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

 

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

 

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

 

입력

 

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

 

출력

 

꽃을 심기 위한 최소 비용을 출력한다.

 

#include<bits/stdc++.h>

using namespace std;

//1.변수 목록
//화단의 정보를 입력받을 2차원 정수행렬 a
//화단의 길이를 입력받을 N
//상하좌우로 움직이기 위한 배열 dy[4],dx[4]
int ret = 987654321,N,visited[10][10],a[10][10];
int dy[4]= {-1,0,1,0};
int dx[4] = {0,1,0,-1};

void dfs(int y,int x,int sum,int cnt)
{
    sum += a[y][x];   
    for(int i=0; i < 4; i++)
    {
        sum = sum + a[y + dy[i]][x + dx[i]];
        visited[y + dy[i]][x + dx[i]] = 1;
        for(int j =0; j < 4; j++) if(!visited[y + dy[i]][x + dx[i]]) visited[y + dy[i]][x + dx[i]] =1;
    }
    if(cnt == 3) 
    {
        ret = min(ret,sum);
        return;
    }
    for(int i = 1; i < N-1; i++)
    {
        for(int j = 1; j <N-1; j++)
        {
            if(!visited[i][j]) dfs(i,j,sum,cnt+1);
        }
    }
}

int main()
{
    cin >> N;
    for(int i =0; i < N; i++)
    {
        for(int j=0; j < N; j++) cin >> a[i][j];
    }
    
    for(int i =1; i < N-1; i++)
    {
        for(int j =1; j < N-1; j++) 
        {
            if(!visited[i][j]) 
            {
                dfs(i,j,0,1);
                memset(visited,0,sizeof(visited));
            }
        }
    }
    cout << ret;

}

 

1시간을 투자하여 먼저 생각하여 풀어보았으나,..

 

 

예제 결과를 통과못하였다..

 

강의 실습코드를 보며 분석해보자

 

강의실습코드

 

#include <bits/stdc++.h>

using namespace std;
int n, ret =987654321, v[20][20], p[20][20], dy[4] = {-1,1,0,0},dx[4] = {0,0,-1,1};

//탐색하는 꽃주변의 값더하는 함수
int setFlower(int y, int x)
{
    v[y][x] = 1;
    int s = p[y][x];
    for (int i =0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        v[ny][nx] = 1;
        s += p[ny][nx];
    }
    return s;
}

//탐색하는 꽃이 심어질수 있는지 확인하는 함수
bool check(int y, int x)
{
    if(v[y][x]) return 0;
    for(int i =0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny <0 || ny >=n || nx < 0 || nx >= n || v[ny][nx]) return false;
    }
    return true;
}

//재귀함수로 방문한 꽃의 경로를 지워줄 함수
void eraseFlower(int y,int x)
{
    v[y][x] = 0;
    for (int i =0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        v[ny][nx] =0;
    }
}

//완전탐색으로 심어질수있는 3개의 꽃의 합을 검사하는 재귀함수
void flower(int cnt,int hap)
{
    if(cnt == 3)
    {
        ret = min(ret, hap);
        return;
    }
    for(int i =0; i < n; i++)
    {
        for(int j =0; j < n; j++)
        {
            if(check(i,j))
            {
                flower(cnt+1,hap + setFlower(i,j));
                eraseFlower(i,j);
            }
        }
    }
}

int main()
{
    cin >> n;
    for(int i =0; i < n; i++)
    {
        for(int j =0; j <n; j++)
        {
            cin >> p[i][j];
        }
    }
    flower(0,0);
    cout << ret;
}

 

용도마다 함수를 나누어 선언하여서 상당히 깔끔한 코드다!

 

이 코드의 작동방식을 순서대로 나열하면 이렇다.

 

1.꽃밭의 길이를 입력받는다.

2.꽃밭의 길이만큼 각각 꽃밭의 값을 입력받는다.

3.재귀함수인 flower() 함수를 호출한다.

4.void flower(int cnt,int hap)

4-1. 만약 cnt가 3이 될시 심은 꽃이 3개가 되는 것이므로
최솟값을 저장하는 ret과 hap을 비교하여 작은 값을 ret에 저장후 리턴.

4-2. 꽃밭의 전체크기만큼 반복문

4-2-1. 만약 check(i,j) 함수의 true 일시

bool check(int y,int x) 함수

방문한 경로를 저장한 배열 v[y][x] 값이 1이거나 해당좌표에서 상하좌우 4방향의 v[ny][nx] 값이 있을 경우 false를 반환,아닐 경우 true를 반환

4-2-1-1. flower의 매개변수 cnt의 값을 +1 증감 및 매개변수 hap 의 값에 setFlower(i,j) 값을 증감시켜 호출

int setFlower(int y,int x) 함수

y,x 값에 위치한 방문배열 v[y][x]의 값을 1로 대입시켜주고, 상하좌우 v[ny][nx] 의 값도 1로 대입시켜준다.

그리고 a[y][x] 의 값과 상하좌우 a[ny][nx] 의 값을 모두 더하여서 반환해준다.

4-2-1-2. eraseFlower(i,j) 를 호출시켜준다.

void eraseFlower(int y,int x) 함수

y,x 값에 위치한 방문배열 v[y][x]의 값을 0으로 대입시켜주고, 상하좌우 v[ny][nx] 의 값도 0으로 대입시켜준다.

방문한 곳을 초기화시켜주는 함수이다.

5.최솟값 ret을 출력

 

내 코드가 제대로 결과값을 출력하지 못하였던 이유는 탐색을 한 부분의 방문 배열만 초기화시켜주면 되는데,

 

전부 초기화해버린것과 꽃이 필 부분을 예측하여 반복문부분에서

for(int i =1; i < N-1; i++)
    {
        for(int j =1; j < N-1; j++)

 

라는 범위를 가지고 완전탐색을 돌렸는데,이 경우에는 완전 탐색을 전부 못돌아서 생긴 문제같다!

 

---

 

백준 1198 문제 - 컴백홈

 

난이도

 

한수는 캠프를 마치고 집에 돌아가려 한다.

 

한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다.

(단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.)

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

 

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다.

 

T로 표시된 부분은 가지 못하는 부분이다.

 

문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

 

입력

 

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다.

두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

 

출력

 

첫 줄에 거리가 K인 가짓수를 출력한다.

 

실습코드

 

#include <bits/stdc++.h>

const int Max_n = 9;
char a[Max_n][Max_n];
int visited[Max_n][Max_n],R,C,K,Cnt;
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};

using namespace std;

void dfs(int y,int x)
{
    if((y == 0 && x == C-1) && visited[y][x] == K) 
    {
        Cnt++;
        return;
    }

    for(int i =0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny >= R || ny <0 || nx >= C || nx < 0 || visited[ny][nx] || a[ny][nx] == 'T') continue;

        visited[ny][nx] = visited[y][x] +1;
        dfs(ny,nx);
        visited[ny][nx] = 0;
    }
}

int main()
{
    cin >> R >> C >> K;

    for(int i =0; i < R; i++)
    {
        string str;
        cin >> str;
        for(int j= 0; j < C; j++) a[i][j] = str[j];        
    }

    visited[R-1][0] = 1;
    dfs(R-1,0);

    cout << Cnt;
}

 

 

진짜 오랜만에 맞췄다 ㅠㅠ 비록 제일 쉬운 단계지만 감격...

 

이 문제는 정말 간단하다.

 

코드의 작동방식을 살펴보자

 

1. 행렬의 세로길이 및 가로길이를 입력받는다.

2. 세로길이와 가로길이만큼의 행렬의 정보를 입력받는다.

3. 시작점은 맨왼쪽 맨아래에서 시작하므로 R-1,0 부터 탐색을 시작한다. 이 수를 dfs 함수안에 넣어 호출한다.

void dfs(int y,int x)

y,x 좌표에서 상하좌우로 탐색하고 탐색하는 좌표 ny,nx 에 해당하는 visited[ny][nx] = visited[y][x] +1 을 해줌으로서

해당 좌표까지 몇번 탐색한지 알 수 있다.

그리고 visited[ny][nx] 의 값을 0으로 대입시켜주어 다음 dfs 탐색이 제대로 돌게 하여준다.

계속 탐색하여 목표지점 맨 오른쪽 위 좌표(0,C-1)에 도달하였을 경우 visited[y][x] 의 값이 K가 될 경우

문제의 조건을 만족시키므로 목표지점까지 K번 이동한 경우의 수를 카운트할 변수 Cnt를 증감시켜준다.

4. 탐색이 종료되면 결과값 Cnt를 출력시켜준다.

 

이 문제의 핵심은 dfs 탐색을 하고 난뒤에, 탐색한 경로의 visited 배열을 초기화시켜주는 것이다.

 

내가 푼거랑 강의실습코드랑 다를 수도 있으니, 한번 비교해보자!

 

강의실습코드

 

#include<bits/stdc++.h>
using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, k, visited[10][10]; 
char a[10][10];
string s; 
int go(int y, int x){
	if(y == 0 && x == m - 1){
		if(k == visited[y][x]) return 1;
		return 0; 
	}
	int ret = 0; 
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx] || a[ny][nx] == 'T')continue;
		visited[ny][nx] = visited[y][x] + 1; 
		ret += go(ny, nx);
		visited[ny][nx] = 0;
	}
	return ret; 
}
int main(){
	cin >> n >> m >> k; 
	for(int i = 0; i < n; i++){
		cin >> s; 
		for(int j = 0; j < m; j++){
			a[i][j] = s[j];
		}
	} 
	visited[n - 1][0] = 1; 
	cout << go(n - 1, 0) << "\n";
}

 

탐색하는 함수의 반환형이 int인것 빼면 다른것이 없다! 훌륭하다 ㅎㅎㅎ