1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <vector>
using namespace std;
int cnt;
const int coverType[4][3][2] = {
    {{0,0}, {0,1}, {1,1}},    // 블록이 회전하는 4가지 형태 
    {{0,0}, {1,0}, {1,1}},
    {{0,0}, {1,0}, {1,-1}},
    {{0,0}, {0,1}, {1,0}}
};
bool set(vector<vector<int> >& board, int y, int x, int type, int delta)
{
    bool state = true;
    for (int i = 0; i < 3; i++)
    {
        int colMax = board.size();
        int rowMax = board[0].size();
        const int ny = y + coverType[type][i][0];
        const int nx = x + coverType[type][i][1];
        if (ny < 0 || ny >= colMax ||
            nx < 0 || nx >= rowMax)
            state = false;
        else if ((board[ny][nx] += delta) > 1)    // delta = 1 일 때, 블록을 덮는다. 
            state = false;                        // delta = -1 일 때, 블록을 치운다. 
    }
    return state;
}
int Solution(vector<vector<int> >& board)
{
    if (cnt % 3 != 0) return 0;    // 기저 사례. 비어이는 블록의 수가 3의 배수가 아닐 경우 반드시 실패
    int col = -1, row = -1;
    int colMax = board.size();    // 행 길이
    int rowMax = board[0].size();    // 열 길이
    for (int i = 0; i < colMax; i++)
    {
        for (int j = 0; j < rowMax; j++)    // 비어있는 칸 중 좌측 상단을 먼저 
        {
            if (board[i][j] == 0)
            {
                col = i;
                row = j;
                break;
            }
        }
        if (col != -1) break;    // 2중 for문 탈출 
    }
    if (col == -1) return 1;    // 기저 사례. 비어있는 칸이 없으므로 1 증가
    int ret = 0;
    for (int i = 0; i < 4; i++)
    {
        if (set(board, col, row, i, 1))    // 비어있는 칸에 블록을 맞춰본다 
            ret += Solution(board);
        set(board, col, row, i, -1);
    }
    return ret;
}
int main(void)
{
    int testcase;
    cin >> testcase;
    while (testcase--)
    {
        int a, b;
        cin >> a >> b;
        vector<vector<int>> board(a);
        cnt = 0;
        for (int i = 0; i < a; i++)
        {
            for (int j = 0; j < b; j++)
            {
                char block;
                cin >> block;
                if (block == '#')    // 막힌 칸을 1로 치환 
                    board[i].push_back(1);
                else if (block == '.')    // 비어있는 칸을 0으로 치환 
                {
                    board[i].push_back(0);
                    cnt++;
                }
            }
        }
        cout << Solution(board) << endl;
        board.clear();
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
  
 

 

 

알고리즘 200일 프로젝트 - 4day

알고리즘 문제해결 전략 6.5 게임판 덮기(ID:BOARDCOVER)

피크닉 문제에서 적용한 재귀함수와 유사한 형태로 구현할 수 있는 문제였다.

내가 생각한 아이디어와 책에서 제시한 아이디어의 접근방법은 비슷했으나,

중복을 신경쓰지 못하여 원하는 출력을 얻지 못하였다. 꾸준히 복습하여 내것으로 만들도록 해야겠다. 

내일도 열심히!

 

 

저작자표시

'알고리즘 > algospot' 카테고리의 다른 글

알고리즘 문제해결전략 예제: 외발 뛰기 (ID: JUMPGAME)  (0) 2020.05.22
알고리즘 문제해결전략 문제7.4 울타리 잘라내기 (ID: FENCE)  (0) 2020.05.09
알고리즘 문제해결전략 문제7.2 쿼드 트리 뒤집기 (ID: QUADTREE)  (0) 2020.05.09
알고리즘 문제해결전략 문제6.8 시계 맞추기(ID: CLOCKSYNC)  (0) 2020.04.10
알고리즘 문제해결전략 문제6.3 소풍(ID: PICNIC)  (0) 2020.04.09

문제

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

  • (태연,제시카) (써니,티파니) (효연,유리)
  • (태연,제시카) (써니,유리) (효연,티파니)

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

출력

각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstring>
using namespace std;
 
bool areFriend[10][10];    // 친한친구 배열
int student;    // 학생 수
int Solution(bool taken[10])
{
    int firstFree = -1;
    for (int i = 0; i < student; i++)
        if (taken[i] == false)    // i = 0~(student-1) 까지 전체 학생을 검사하여 짝을 짓지못한 학생을 찾아낸다.
        {
            firstFree = i;
            break;
        }
    if (firstFree == -1) return 1;    // 학생들이 모두 짝을 이루었으므로 1 증가
    int ret = 0;    // ret : 짝을 지을수 있는 경우의 수
    for(int i=firstFree+1; i<student; i++)
        if (!taken[firstFree] && !taken[i] && areFriend[firstFree][i])
        {
            taken[firstFree] = taken[i] = true;    // 아직 짝을 짓지못한 친한 학생 taken[firstFree]와 taken[i]를
                                                // 짝을 지은 학생(true)로 갱신하여 Solution 함수를 재귀호출한다.
 
            ret += Solution(taken);    // 짝을 지은 학생들을 true처리하고 함수를 재호출한다. 
 
            taken[firstFree] = taken[i] = false; // 아직 짝을 짓지못한 학생들중 taken[firstFree] 학생과 
                                                 // 친한 학생을 더 찾기위해 false로 초기화해준다.
        }
    return ret;
}
 
int main(void)
{
    int testcase;
    bool taken[10];
    cin >> testcase;
    while (testcase--)
    {
        int cpNum;
        cin >> student >> cpNum;
        memset(areFriend, false, sizeof(areFriend));    // 친한 친구 배열 false로 초기화
        memset(taken, false, sizeof(taken));    // 학생들의 상태를 false로 초기화
        while (cpNum--)
        {
            int a, b;
            cin >> a >> b;
            areFriend[a][b] = true;
            areFriend[b][a] = true;
        }
        cout << Solution(taken) << endl;;
    }
    return 0;
}
 cs
 
 
  

 

알고리즘 200일 프로젝트 - 3day

알고리즘 문제해결 전략 6.3 소풍(ID:PICNIC)

난이도 하 문제였음에도 불구하고 이해하는데 매우 힘들었다. ㅠㅠ

내일도 열심히!

'알고리즘 > algospot' 카테고리의 다른 글

알고리즘 문제해결전략 예제: 외발 뛰기 (ID: JUMPGAME)  (0) 2020.05.22
알고리즘 문제해결전략 문제7.4 울타리 잘라내기 (ID: FENCE)  (0) 2020.05.09
알고리즘 문제해결전략 문제7.2 쿼드 트리 뒤집기 (ID: QUADTREE)  (0) 2020.05.09
알고리즘 문제해결전략 문제6.8 시계 맞추기(ID: CLOCKSYNC)  (0) 2020.04.10
알고리즘 문제해결전략 문제6.5 게임판 덮기(ID: BOARDCOVER)  (0) 2020.04.09

+ Recent posts

티스토리툴바