[2017 카카오코드 본선]리틀 프렌즈 사천성 C++

https://programmers.co.kr/learn/courses/30/lessons/1836

코딩테스트 연습 - 리틀 프렌즈 사천성

- TC 4개는 통과/ 제출실패

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

struct node {
    int y, x, bang, le;
};

string solution(int m, int n, vector<string> board) {
    string answer = "";

    int direct[4][2] = {
        -1,0,
        1,0,
        0,-1,
        0,1
    };

    vector<vector<char>>Check(10);
    
    //map<char, pair<int,int>>map;
    vector<vector<pair<int, int>>>pairVec(100);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            char target = board[i][j];
            pairVec[target].push_back(make_pair(i, j));
        }
    }

    int sun = 0;
    while (1) {
        bool exist = false;
        for (int i = 'A'; i <= 'Z'; i++) {
            if (pairVec[i].size() == 2) {
                char target = i;
                int sty = pairVec[i][0].first;
                int stx = pairVec[i][0].second;
                int endy = pairVec[i][1].first;
                int endx = pairVec[i][1].second;

                queue<node>q;
                int used[100][100] = { 0 };
                q.push({ sty, stx,-1,0 });
                used[sty][stx] = 1;

                int flag = 0;
                while (!q.empty()) {
                    if (flag == 1) break;

                    node now = q.front();
                    q.pop();

                    for (int x = 0; x < 4; x++) {
                        int dy = now.y + direct[x][0];
                        int dx = now.x + direct[x][1];
                        if (dy < 0 || dx < 0 || dy >= m || dx >= n) continue;
                        if (used[dy][dx] == 1) continue;
                        if (board[dy][dx] != '.' && board[dy][dx] != target) continue;

                        if (now.bang != x) {
                            if (now.le + 1 > 2) break;
                            else q.push({ dy, dx, x, now.le + 1 });
                        }
                        else if (now.bang == x) q.push({ dy, dx, x, now.le });

                        used[dy][dx] = 1;

                        if (dy == endy && dx == endx) {
                            exist = true;
                            Check[sun].push_back(i);
                            board[sty][stx] = board[endy][endx] = '.';
                            pairVec[i].clear();
                            flag = 1;
                            break;
                        }
                    }
                }
            }
        }
        sun++;
        if (!exist) break;
    }

    if (Check[0].empty()) 
        answer = "IMPOSSIBLE";

    for (int i = 0; i < Check.size(); i++) {
        if (Check[i].empty()) break;
        sort(Check[i].begin(), Check[i].end());
        for (int j = 0; j < Check[i].size(); j++)
            answer += Check[i][j];
    }

    return answer;
}

 

- A-Z탐색 반복 X, A부터 탐색하다가 짝이 맞았을때 다시 A부터 재탐색

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

struct node {
    int y, x, bang;
};

string solution(int m, int n, vector<string> board) {
    string answer = "";

    int direct[4][2] = {
        -1,0,
        1,0,
        0,-1,
        0,1
    };
	    
    //map<char, pair<int,int>>map;
    map<char, node > pairVec;

	//알파벳별 시작위치만 저장 (도착지 bfs탐색)
    for (int i = 0; i < m; i++) { 
        for (int j = 0; j < n; j++) {
            char target = board[i][j];
            if(target>='A' && target<='Z')
				pairVec[target] = { i, j };
		}
	}

	int sun = 0;
	while (1) {
		bool exist = false;
		for (int i = 'A'; i <= 'Z';i++) {
			if (pairVec.count(i) <= 0) continue;
			char target = i;
			int sty = pairVec[i].y;
			int stx = pairVec[i].x;

			queue<node>q;
			vector<vector<int>> turnCheck(m, vector<int>(n, 999)); // 꺾은 횟수 저장

			q.push({ sty, stx, -1 });
			turnCheck[sty][stx] = 0;

			int flag = 0;
			while (!q.empty()) {

				node now = q.front();
				q.pop();

				if (flag == 1 && board[now.y][now.x] == target) {
					exist = true;
					answer += target;
					board[sty][stx] = board[now.y][now.x] = '.';
					pairVec.erase(target);
					i = 'A'-1;
					break;
				}

				flag = 1;

				for (int x = 0; x < 4; x++) {
					int dy = now.y + direct[x][0];
					int dx = now.x + direct[x][1];
					int cnt = turnCheck[now.y][now.x];

					if (now.bang != -1 && now.bang != x)
						cnt++;

					if (dy < 0 || dx < 0 || dy >= m || dx >= n) continue;
					//if (used[dy][dx] == 1) continue;
					if (board[dy][dx] != '.' && board[dy][dx] != target) continue;

					if (cnt >= 2) continue;

					if (turnCheck[dy][dx] >= cnt) {
						q.push({ dy,dx,x });
						turnCheck[dy][dx] = cnt;
					}
				}
			}
		}
		if (exist) continue;

		if (!pairVec.empty())
			answer = "IMPOSSIBLE";

		return answer;
	}
}

int main() {
	cout << solution(5, 5, { "FGHEI", "BAB..", "D.C*.", "CA..I", "DFHGE" }) << '\n'; //ABCDFHGIE
    //cout << solution(2, 4, { "NRYN", "ARYA" }) << '\n'; //RYAN
    //cout << solution(2, 2, { "AB", "BA" }) << '\n';
    //cout << solution(2, 2, { "ZA", "ZA" }) << '\n'; //"AZ"
    //cout << solution(1, 2, { "AA" }) << '\n'; // "A"
	return 0;
}