객체지향프로그래밍 과제3 총정리

 

객체지향프로그래밍 1번

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void sorted_merge(vector<string> &first, vector<string> &second) {
    auto it1 = first.begin(), it2 = second.begin();
    while (it1 != first.end() && it2 != second.end()) {
        if (*it1 < *it2)
            it1++;
        else if (*it1 >= *it2) {
            it1 = first.insert(it1, *it2);
            it2++;
        }
    }
    while (it2 != second.end()) {
        first.insert(first.end(), *it2);
        it2++;
    }
}

int main() {
    int m, n;
    string str;
    vector<string> first, second;
    cin >> m;
    // m개의 영문자열이 사전식 순서로 정렬되어 입력된다.
    for (int i=0; i<m; i++)  {
        cin >> str;
        first.push_back(str);
    }
    cin >> n;
    // n개의 영문자열이 사전식 순서로 정렬되어 입력된다.
    for (int i=0; i<n; i++)  {
        cin >> str;
        second.push_back(str);
    }

    sorted_merge(first, second);

    // m+n개의 문자열이 사전식 순서로 정렬되어 출력되어야 한다.
    for (auto item: first)
        cout << item << " ";
    cout << endl;
    return 0;
}

 

해당 문제에서는 sorted_merge 함수에 대해서 코드를 채운 것입니다. sorted_merge 함수는 m개의 사전식 순서로 정렬된 영문자열과, 다시 n개의 사전식 순서로 정렬된 문자열을 입력받아 벡터 first와 second에 저장한 것으로 sorted_merge는 두 벡터에 저장된 문자열을 벡터 first에 정렬된 상태로 합병하는 일을 하는 것입니다. 

 

sorted_merge에는 합병을 하기 위해 두 개의 정렬된 벡터를 인자로 받습니다.

 

while루프는 첫 번째 벡터와 두 번째 벡터 모두의 끝에 도달할 때까지 실행합니다. 두 벡터를 비교하여 현재 첫 번째 벡터의 요소가 두 번째 벡터의 요소보다 작으면 첫 번째 벡터 반복자를 다음 요소로 이동시킵니다.

 

만약 두 번째 벡터의 요소가 첫 번 벡터의 요소보다 작거나 같으면, 해당 요소를 첫 번째 벡터에 삽입합니다. 그 후, 첫 번째 벡터의 반복자를 새로 삽입된 요소를 가리키도록 갱신하고, 두 번째 벡터의 반복자도 다음 요소로 이동시킵니다. 

 

it1 = first.insert(it1, *it2); it2++;

 

두 번째 벡터의 요소들이 모두 처리된 후에도 첫 번째 벡터에 추가할 요소가 남아있다면, 나머지 모든 요소들을 첫 번째 벡터의 끝에 삽입합니다. 

 

객체지향프로그래밍 2번

#include <iostream>
#include <vector>
using namespace std;

void compute_set(vector<int> &A, vector<int> &B) {
    auto it1 = A.begin(), it2 = B.begin();
    while (it1 != A.end() && it2 != B.end()) {
        if (*it1 < *it2)
            it1++;
        else if (*it1 > *it2) {
            it1 = A.insert(it1, *it2);
            it2++;
        }
        else {
            it1 = A.erase(it1);
            it2++;
        }
    }
    while (it2 != B.end()) {
        A.insert(A.end(), *it2);
        it2++;
    }
}

int main() {
    int m, n, k;
    vector<int> first, second;
    cin >> m;
    // m개의 정수가 오름차순으로 정렬되어 입력된다.
    for (int i=0; i<m; i++)  {
        cin >> k;
        first.push_back(k);
    }
    cin >> n;
    // n개의 정수가 오름차순으로 정렬되어 입력된다.
    for (int i=0; i<n; i++)  {
        cin >> k;
        second.push_back(k);
    }

    compute_set(first, second);

    for (auto item: first)
        cout << item << " ";
    cout << endl;
    return 0;
}

이 compute_set 함수는 두 개의 정렬된 벡터 'A'와 'B'를 인자로 받아서, 두 집합의 합집합을 계산하는 작업을 수행합니다. 여기서 합집합은 각 원소가 중복되지 않는 형태로 취합됩니다.

 

it1과 it2라는 두 개의 반복자를 사용하여 각각 'A'와 'B'를 가리킵니다.

 

while루프는 두 벡터의 끝에 도달될 때까지 실행됩니다. it1이 가리키는 값이 it2가 가리키는 값보다 작으면 it1을 다음 요소로 이동시킵니다. 왜냐하면 작은 값은 이미 'A'벡터에 있으므로 중복을 허용하지 않아야 합니다.

 

 

반대로 it1이 가리키는 값이 it2가 가리키는 값보다 크다면, it2가 가리키는 값을 A벡터에 삽입합니다. 그리고 it2를 다음 요소로 이동합니다. 

 

만약 it1와 it2가 같다면 it1이 가리키는 값은 이미 A벡터에 존재하므로 it1을 삭제합니다. 그리고 it2를 다음 요소로 이동합니다. 두 번째 while루프는 b벡터를 나머지 요소들을 A벡터의 끝에 추가합니다. 

 

 

객체지향프로그래밍 3

 

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
using namespace std;

vector<string> words;
vector<vector<int>> lineNums;
vector<string> text;

void makeIndex(string fileName);
void handle_find(string keyword);
void addWord(string word, int lineNum);
int findWord(string keyword);
void saveAs(string fileName);
vector<string> split_line(string line, char delimiter);
string trim(string str);
void tolowercase(string &str);

int main() {
    string command;
    while(true)		{
        cout << "$ ";
        cin >> command;
        if (command == "read")	{
            string fileName;
            cin >> fileName;
            makeIndex(fileName);
        }
        else if (command == "exit")
            break;
        else if (command == "find")	{
            string keyword;
            cin >> keyword;
            tolowercase(keyword);
            handle_find(keyword);
        }
    }
    return 0;
}

void handle_find(string keyword) {
    int index = findWord(keyword);
    if (index !=-1)  {
        cout << "The word " << keyword << " appears " <<
             lineNums[index].size()  << " times in lines: " << endl;
        for (auto v : lineNums[index]) {
            cout << v << ": ";
            cout << text[v] << endl;
        }
    }
    else
        cout << "The word " << keyword << " doesn’t appear." << endl;
}

void makeIndex(string fileName) {
    ifstream theFile(fileName);
    int lineNum = 0;
    string line;
    while(getline(theFile, line)) {
        text.push_back(line);
        vector<string> tokens = split_line(line, ' ');
        for (string s : tokens) {
            string str = trim(s);   // explain students why 'tolowercase(trim(s))' not works.
            if (s.length() > 2) {
                tolowercase(str);
                addWord(str, lineNum);
            }
        }
        lineNum++;
    }
    theFile.close();
}

vector<string> split_line(string line, char delimiter)
{
    vector <string> tokens;
    stringstream sstream(line);
    string str;

    while(getline(sstream, str, delimiter))
        tokens.push_back(str);
    return tokens;
}


void addWord(string word, int lineNum) {
    int index = findWord(word);
    if (index > -1) {
        if (find(lineNums[index].begin(), lineNums[index].end(), lineNum)==lineNums[index].end())
            lineNums[index].push_back(lineNum);
    }
    else {
        words.push_back(word);
        vector<int> tmp = {lineNum};
        lineNums.push_back(tmp);
    }
}


int findWord(string keyword) {
    for (int i=0; i<words.size(); i++)
        if (words[i] == keyword)
            return i;
    return -1;
}


void saveAs(string fileName) {
    ofstream outFile(fileName);
    for (int i=0; i<words.size(); i++) {
        outFile << words[i] << endl;
        for (auto c: lineNums[i])
            outFile << c << " ";
        outFile << endl;
    }
    outFile.close();
}

string trim(string str) {
    int s = 0, t = str.length()-1;;
    while(s<str.length() && !isalnum(str[s]))
        s++;
    while(t>=0 && !isalnum(str[t]))
        t--;
    if (s<=t)
        return str.substr(s, t-s+1);
    else
        return "";
}

void tolowercase(string &str) {
    for (int i=0; i<str.length(); i++)
        str[i] = tolower(str[i]);
}

 

객체지향프로그래밍 4번

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

int N;
vector<vector<int>> board;

bool check(int x, int y);

int main()
{
    ifstream infile("board.txt");
    infile >> N;
    for (int i=0; i<N; i++) {
        vector<int> row(N);
        board.push_back(row);
        for (int j = 0; j<N; j++)
            infile >> board[i][j];
    }
    infile.close();

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (board[i][j] == 0)
                continue;

            // check if board[i][j] is an end of 5-consecutive stone of same color
            if (check(i, j)) {
                if (board[i][j] == 1)
                    cout << "black";
                else
                    cout << "white";
                return 0;
            }
        }

    }
    cout << "not finished";
    return 0;
}

vector<vector<int>> offset{
        {1, -1},
        {1, 0},
        {1, 1},
        {0, 1}
};

bool check(int x, int y) {
    // check four directions, SW, S, SE, E
    int mystone = board[x][y];
    for (int dir=0; dir<4; dir++) {
        int d = 1;
        while (d<5 && x + d*offset[dir][0] < N
               && y + d*offset[dir][1] >= 0
               && y + d*offset[dir][1] < N) {
            if (board[x+d*offset[dir][0]][y+d*offset[dir][1]] != mystone)
                break;
            d++;
        }
        if (d == 5)
            return true;
    }
    return false;
}

이 코드는 바둑판의 상태를 나타내는 2차원 벡터 board가 주어졌을 때, 해당 바둑판에 어떤 색의 돌이 5개가 연달아 놓인 상태인지를 확인하는 프로그램입니다.

코드는 다음과 같은 동작을 수행합니다:

파일로부터 바둑판의 크기 N과 각 위치의 돌의 상태를 읽어와서 board 벡터에 저장합니다.
이중 반복문을 사용하여 모든 위치를 탐색하면서, 돌이 놓여 있는 경우에만 check 함수를 호출합니다.
check 함수는 현재 위치에서 4개의 방향으로 돌이 연속된 상태인지를 확인합니다. 만약 어떤 색의 돌이 5개가 연속된 상태라면, 해당 색을 출력하고 프로그램을 종료합니다.
만약 모든 위치를 탐색해도 5개가 연속된 돌을 찾지 못했다면 "not finished"를 출력합니다.
이 코드는 주어진 바둑판의 상태에서 특정 위치에서부터 시작하여 4개의 방향으로 돌이 5개가 연속된 상태를 확인하여 그 여부를 결정하는 것입니다.

 

N: 바둑판의 크기를 나타내는 변수로, int 형으로 선언되어 있습니다.
board: 바둑판의 상태를 저장하는 2차원 벡터로, 바둑판의 각 칸에 놓인 돌의 상태를 나타냅니다.
check(int x, int y): 주어진 위치 (x, y)에서부터 시작하여 4개의 방향으로 돌이 5개가 연속된 상태인지를 확인하는 함수입니다. 이 함수는 bool 타입을 반환합니다. 연속된 5개의 돌이 있는 경우 true를 반환하고, 그렇지 않은 경우 false를 반환합니다.
offset: 주어진 위치에서 4개의 방향(남서, 남쪽, 남동, 동쪽)으로 이동하기 위한 상대적인 좌표의 집합을 나타내는 2차원 벡터입니다.
main(): 프로그램의 시작점으로, 바둑판의 크기와 상태를 파일에서 읽어와 board 벡터에 저장한 후, 모든 위치를 탐색하면서 check 함수를 호출하여 5개의 돌이 연속된 상태를 확인합니다. 이후 해당 결과에 따라 적절한 출력을 수행합니다.

 

객체지향프로그래밍 5번

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

class Point {
public:
    int x, y;
};

class LineSegment {
public:
    Point s, t;
    bool is_horizontal() {
        return s.x == t.x;
    }

    bool intersecting(LineSegment other, Point &p) {
        if (is_horizontal() == other.is_horizontal())
            return false;
        if (is_horizontal()) {
            if (other.s.x <= s.x && other.t.x >= s.x &&
                    s.y <= other.s.y && t.y >= other.s.y) {
                p.x = s.x, p.y = other.s.y;
                return true;
            }
            return false;
        }
        else {
            if (s.x <= other.s.x && t.x >= other.s.x &&
                other.s.y <= s.y && other.t.y >= s.y) {
                p.x = other.s.x, p.y = s.y;
                return true;
            }
            return false;
        }
    }
};

int main() {
    int N;
    vector<LineSegment> lines;
    cin >> N;
    for (int i=0; i<N; i++) {
        LineSegment line;
        cin >> line.s.x >> line.s.y >> line.t.x >> line.t.y;
        lines.push_back(line);
    }

    for (int i=0; i<N; i++) {
        for (int j=i+1; j<N; j++) {
            Point p;
            if (lines[i].intersecting(lines[j], p))
                cout << '[' << p.x << ", " << p.y << ']' << endl;
        }
    }
}

이 코드는 두 선분이 주어졌을 때 두 선분이 교차하는 지점을 찾는 프로그램입니다.

여기서 사용되는 주요 클래스는 Point와 LineSegment입니다.

Point: 점을 나타내는 클래스로, x와 y 좌표를 가지고 있습니다.
LineSegment: 선분을 나타내는 클래스로, 시작점 s와 끝점 t를 가지고 있습니다. 또한, is_horizontal 함수는 해당 선분이 수평인지를 판별합니다. intersecting 함수는 다른 선분과 교차하는지를 확인하고, 교차하는 경우 교차점의 좌표를 반환합니다.
main 함수에서는 다음과 같은 작업을 수행합니다:

입력으로 선분의 수 N과 각 선분의 좌표를 받습니다.
입력받은 선분들을 lines 벡터에 저장합니다.
이중 반복문을 통해 모든 선분 쌍을 비교하며 교차하는 지점을 찾습니다.
교차하는 경우 해당 교차점의 좌표를 출력합니다.
이 코드는 각 선분의 시작점과 끝점을 이용하여 두 선분이 교차하는 지점을 계산하는 방식으로 동작합니다.

 

객체지향프로그래밍 6번

#include <iostream>
#include <vector>
using namespace std;

class Point {
public:
    int x, y;
};

vector<vector<int>> offset{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

bool is_horizontal(Point s, Point t) {
    return s.x == t.x;
}

bool intersecting(Point s1, Point t1, Point s2, Point t2)  {
    if (is_horizontal(s1, t1) && s1.y > t1.y || !is_horizontal(s1, t1) && s1.x > t1.x)
        swap(s1, t1);
    if (is_horizontal(s2, t2) && s2.y > t2.y || !is_horizontal(s2, t2) && s2.x > t2.x)
        swap(s2, t2);

    if (is_horizontal(s1, t1) && is_horizontal(s2, t2))
        return !(s1.x != s2.x || t1.y > s2.y || t2.y > s1.y);
    else if (!is_horizontal(s1, t1) && !is_horizontal(s2, t2))
        return !(s1.y != s2.y || t1.x > s2.x || t2.x > s1.x);
    else if (is_horizontal(s1, t1))
        return s1.y <= s2.y && t1.y >= s2.y && s2.x <= s1.x && t2.x >= s1.x;
    else
        return s1.x <= s2.x && t1.x >= s2.x && s2.y <= s1.y && t2.y >= s1.y;
}

bool check_last(Point p, Point q, Point r) {
    if (is_horizontal(p, q) != is_horizontal(q, r))
        return true;
    if (is_horizontal(p, q) && (r.y > p.y && r.y < q.y || r.y > q.y && r.y < p.y
                    || p.y > q.y && p.y < r.y || p.y > r.y && p.y < q.y))
        return false;
    else if ((r.x > p.x && r.x < q.x || r.x > q.x && r.x < p.x
                    || p.x > q.x && p.x < r.x || p.x > r.x && p.x < q.x))   // both vertical
        return false;
    return true;
}

bool is_valid_move(vector<Point> &points, Point &p) {
    for (auto i=0; i<(int)points.size()-2; i++) {
        if (intersecting(points[i], points[i+1], points[points.size()-1], p))
            return false;
    }
    if (points.size() > 1) {
        return check_last(points[points.size()-2], points[points.size()-1], p);
    }
    return true;
}

int main() {
    vector<Point> points;
    Point cur;
    cur.x = 0, cur.y = 0;
    points.push_back(cur);
    while(1) {
        int dir, len;
        cin >> dir >> len;
        if (dir==-1 && len==-1)
            break;
        Point next;
        next.x = cur.x + len*offset[dir][0];
        next.y = cur.y + len*offset[dir][1];

        if (is_valid_move(points, next)) {
            cout << next.x << " " << next.y << endl;
            points.push_back(next);
            cur = next;
        }
        else
            cout << "invalid move" << endl;
    }
}

이 코드는 주어진 방향과 길이에 따라 포인트를 이동하고, 이동된 포인트들이 서로 교차하지 않으면 유효한 이동으로 간주하는 프로그램입니다. 이 코드에서는 다음과 같은 주요 함수와 클래스가 사용됩니다:

Point 클래스: x와 y 좌표를 가지는 점을 나타내는 클래스입니다.
offset: 주어진 방향에 따라 포인트를 이동하기 위한 상대적인 좌표의 집합을 나타내는 2차원 벡터입니다.
is_horizontal(Point s, Point t): 주어진 두 점이 수평 방향에 있는지를 판별하는 함수입니다.
intersecting(Point s1, Point t1, Point s2, Point t2): 주어진 두 선분이 교차하는지를 판별하는 함수입니다.
check_last(Point p, Point q, Point r): 세 점이 주어졌을 때, 세 번째 점이 첫 번째와 두 번째 점을 이은 선분과 교차하는지를 판별하는 함수입니다.
is_valid_move(vector<Point> &points, Point &p): 주어진 점 p가 현재까지 이동된 점들의 경로와 교차하지 않으면 유효한 이동으로 간주하는 함수입니다.
main(): 프로그램의 시작점으로, 사용자로부터 방향과 길이를 입력받아 포인트를 이동시키고, 유효한 이동인지를 판별하는 작업을 수행합니다.
이 코드는 주어진 방향과 길이에 따라 포인트를 이동하고, 이동된 포인트들이 서로 교차하지 않으면 유효한 이동으로 간주합니다. 만약 이동이 유효하지 않으면 "invalid move"를 출력하고, 유효한 경우에는 이동한 포인트의 좌표를 출력합니다.

 

 

객체지향프로그래밍 7번

#include <iostream>
using namespace std;

const int MAX = 100;

int board[MAX][MAX];
int n = 8;

void printBoard();
int countCapturableStone(int i, int j, int);
int countCapturableStoneInDir(int x, int y, int dir, int);
int getValue(int x, int y, int dir, int dist);
int putStone(int x, int y, int turn);
int captureStones(int x, int y, int dir, int turn);
int humanPlay();
int computerPlay();
void initBoard();
void decideWinner();

int main()
{
    int ch;
    while(1) {
        initBoard();
        printBoard();
        while(1) {
            int count = 0;
            count += humanPlay();
            printBoard();
            count += computerPlay();
            printBoard();
            if (count==0)
                break;
        }
        decideWinner();
        cout << "Do you want another game ? ";
        cin >> ch;
        if (ch != 'y' && ch != 'Y')
            break;
    }
}

void decideWinner() {
    int myCount = 0, computerCount = 0;
    for (int i=0; i<n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 1) myCount++;
            else if (board[i][j] == 2) computerCount++;
        }
    }
    if (myCount > computerCount)
        cout << "Congraturation, You win !\n";
    else if (myCount < computerCount)
        cout << "Oops... you lost the game...\n";
    else
        cout << "Tie...\n";
}

void initBoard() {
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            board[i][j] = 0;
    board[3][3] = 1;
    board[3][4] = 2;
    board[4][3] = 2;
    board[4][4] = 1;
}

int humanPlay()
{
    int x, y;
    do {
        cout << "Choose position: ";
        cin >> x >> y;
        if (x==-1 || y==-1)          // 착수 포기
            return 0;
    } while(countCapturableStone(x, y, 1) <= 0);

    return putStone(x, y, 1);
}

int computerPlay() {
    int max = 0, maxx, maxy;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (board[i][j] != 0) continue;
            int count = countCapturableStone(i, j, 2);
            if( count > max) {
                max = count;
                maxx = i;
                maxy = j;
            }
        }
    }
    if (max <= 0)       // 착수포기
        return 0;
    return putStone(maxx, maxy, 2);
}

int putStone(int x, int y, int turn)
{
    int count = 0;
    for (int dir = 0; dir < 8; dir++) {
        if (countCapturableStoneInDir(x, y, dir, turn) > 0)
            count += captureStones(x, y, dir, turn);
    }
    board[x][y] = turn;
    return count;
}

int offset[8][2] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
int captureStones(int x, int y, int dir, int turn) {
    int count = 0;
    int opp = (turn == 1 ? 2 : 1);
    x += offset[dir][0];
    y += offset[dir][1];
    while(board[x][y] == opp)  {
        board[x][y] = turn;
        x += offset[dir][0];
        y += offset[dir][1];
        count++;
    }
    return count;
}

/* 위치 (x, y)에 turn의 돌을 놓았을 때 잡을 수 있는 상대 돌의 개수를 count하여 반환한다. */
int countCapturableStone(int x, int y, int turn)
{
    if (board[x][y] != 0)
        return 0;
    int sum = 0;
    for (int dir=0; dir<8; dir++) {
        sum += countCapturableStoneInDir(x, y, dir, turn);
    }
    return sum;
}

/* 위치 (x, y)에 turn의 돌을 놓았을 때 dir 방향으로 잡을 수 있는 상대 돌의 개수를 count하여 반환한다. */
int countCapturableStoneInDir(int x, int y, int dir, int turn) {
    int d=1, value;
    int opp = (turn == 1 ? 2 : 1);
    while((value = getValue(x,y,dir,d)) == opp)
        d++;
    return (value != turn ? 0 : d-1);
}

int getValue(int x, int y, int dir, int dist)
{
    int newx = x + dist*offset[dir][0];
    int newy = y + dist*offset[dir][1];
    if (newx<0 || newx >=n || newy < 0 || newy >= n)
        return -1;
    return board[newx][newy];
}

void printBoard() {
    printf("\n");
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++)
            cout << board[i][j] << ' ';
        cout << endl;
    }
}

이 코드는 오셀로(Othello) 게임을 구현한 것으로, 사람과 컴퓨터가 번갈아가며 게임을 진행합니다. 코드에서는 오셀로의 규칙을 따라 돌을 놓고, 상대방의 돌을 잡아가며 승부를 결정합니다.

주요 함수와 클래스는 다음과 같습니다:

Point 클래스: 정수형 변수 x와 y를 가지는 좌표를 표현합니다.
initBoard(): 보드를 초기화하고, 초기 위치에 돌을 배치하는 함수입니다.
humanPlay(): 사용자에게 돌을 놓을 위치를 입력받고, 해당 위치에 돌을 놓아 유효한지 검사한 후 보드를 갱신하는 함수입니다.
computerPlay(): 컴퓨터가 돌을 놓을 위치를 계산하고, 해당 위치에 돌을 놓아 유효한지 검사한 후 보드를 갱신하는 함수입니다.
putStone(): 주어진 위치에 돌을 놓고, 해당 위치에 돌을 놓아 유효한지 검사하고 보드를 갱신하는 함수입니다.
countCapturableStone(): 주어진 위치에 돌을 놓았을 때, 상대방의 돌을 잡을 수 있는 개수를 계산하는 함수입니다.
countCapturableStoneInDir(): 주어진 위치와 방향으로부터 상대방의 돌을 잡을 수 있는 개수를 계산하는 함수입니다.
captureStones(): 주어진 위치와 방향으로부터 상대방의 돌을 잡는 함수입니다.
decideWinner(): 게임 종료 후 승자를 결정하는 함수입니다.
printBoard(): 현재 보드 상태를 출력하는 함수입니다.
이 코드를 통해 사용자와 컴퓨터가 번갈아가며 게임을 진행하고, 최종적으로 승자를 결정할 수 있습니다.

 

객체지향프로그래밍 8번

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

vector<string> dict;
char puzzle[16][16];
int N;
vector<string> words;

int offset[8][2] = {{0,1}, {1,1},
                    {1,0}, {1,-1},
                    {0, -1}, {-1, -1},
                    {-1, 0}, {-1, 1} };
bool add_char_at(int x, int y, int dir, int dist, string &str) {
    int xx = x + dist*offset[dir][0];
    int yy = y + dist*offset[dir][1];
    if (xx < 0 || xx >= N || yy < 0 || yy >= N)
        return false;
    str += puzzle[xx][yy];
    return true;
}

void solve() {
    for (int i=0; i<N; i++) {
        for (int j = 0; j < N; j++) {
            for (int dir = 0; dir < 8; dir++) {
                string str = "";
                for (int k = 0; k < N; k++) {
                    if (add_char_at(i, j, dir, k, str)) {
                        if (find(dict.begin(), dict.end(), str) != dict.end()) {
                            if (find(words.begin(), words.end(), str) == words.end())
                                words.push_back(str);
                        }
                    }
                    else
                        break;
                }
            }
        }
    }

    for (auto w: words)
        cout << w << endl;
}

int main() {
    string word;
    ifstream dictfile("dictionary.txt");
    while(dictfile >> word)
        dict.push_back(word);
    dictfile.close();

    ifstream puzzfile("puzzle.txt");
    puzzfile >> N;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            puzzfile >> puzzle[i][j];
        }
    }
    puzzfile.close();
    solve();

    return 0;
}

이 코드는 주어진 사전과 퍼즐 파일을 읽어와서, 퍼즐 파일에 있는 단어들을 찾아내는 프로그램입니다.

주요 함수와 변수는 다음과 같습니다:

add_char_at(int x, int y, int dir, int dist, string &str): 주어진 위치와 방향에서부터 지정된 거리까지 문자를 추가하는 함수입니다.
solve(): 퍼즐 파일에서 단어를 찾아내는 함수입니다. 모든 위치에서 8방향을 탐색하면서 가능한 단어를 찾아내고, 이를 사전과 비교하여 유효한 단어인지 확인한 후 결과를 출력합니다.
main(): 프로그램의 시작점으로, 사전 파일과 퍼즐 파일을 읽어들여서 solve 함수를 호출하여 퍼즐 속 단어들을 찾습니다.
주요 알고리즘은 다음과 같습니다:

8방향을 탐색하여 퍼즐 속에서 가능한 모든 단어를 추출합니다.
추출한 단어가 사전에 존재하는지 확인하고, 존재한다면 words 벡터에 추가합니다.
최종적으로 words 벡터에 저장된 유효한 단어들을 출력합니다.
이 코드를 실행하면 퍼즐 파일에서 찾아낸 단어들이 출력됩니다.