알고리즘/프로그래머스
리틀 프렌즈 사천성
pureworld
2021. 5. 13. 12:46
오답코드
|
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
#include<iostream>
#include <string>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
string answer = "";
vector<string> arr;
int N, M;
int dy[5] = { 0,0,1,0,-1 };
int dx[5] = { 0,1,0,-1,0 };
int alpha[26];
typedef pair<int, int > pii;
int chk[30];
vector< pair < char, pii > >input;
int visited[101][101];
void reset() {
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
visited[i][j] = 0;
}
void Print() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
cout << arr[i][j] << " ";
cout << "\n";
}
cout << "\n";
}
bool BFS(int cy, int cx, char target) {
reset();
queue<pair< pii, pii > > q;
q.push({ {cy,cx},{0,0} });
//cout << "실행 " << " \n";
//cout << cy << " " << cx << " " << " "<<target << " \n";
while (!q.empty()) {
int y = q.front().first.first;
int x = q.front().first.second;
int dir = q.front().second.first;
int cv = q.front().second.second;
q.pop();
visited[y][x] = 1;
//cout << y << " " << x << " " << dir << " " << cv << " \n";
//Print();
if (arr[y][x] == target && !(y==cy && x ==cx )) {
arr[y][x] = '.';
return true;
}
if (arr[y][x] == '*' && !(y == cy && x == cx))
continue;
if (arr[y][x] != '.' && !(y == cy && x == cx))
continue;
if (cv == 1) {
int ny = y + dy[dir];
int nx = x + dx[dir];
if (0 <= ny && ny < N && 0 <= nx && nx < M && !visited[ny][nx] ) {
q.push({ {ny,nx},{dir,cv} });
}
}
else {
for (int i = 1; i <= 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (0 <= ny && ny < N && 0 <= nx && nx < M && !visited[ny][nx]) {
//첫 출발시.
if (dir == 0) {
q.push({ {ny,nx},{i,0} });
continue;
}
//같은방향인 경우
if (dir == i) {
q.push({ {ny,nx},{i,0} });
}
//꺾는 경우
else {
q.push({ {ny,nx},{i,1} });
}
}
}
}
}
return false;
}
string solution(int m, int n, vector<string> board) {
arr = board; N = m; M = n;
//중복제거 알파벳과 좌표넣기
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
if (arr[i][j] != '.' && arr[i][j] != '*') {
if (!alpha[arr[i][j] - 'A']) {
alpha[arr[i][j] - 'A']++;
input.push_back({ arr[i][j],{i,j} });
}
}
}
//알파벳순으로 정렬
sort(input.begin(), input.end());
/*
for (int i = 0; i < input.size(); i++) {
cout << input[i].first << " " << input[i].second.first << " " << input[i].second.second<<"\n";
}
*/
for (int i = 0; i < input.size(); i++) {
char target = input[i].first;
if (chk[target - 'A'])
continue;
int y = input[i].second.first;
int x = input[i].second.second;
if (BFS(y, x, target)) {
arr[y][x] = '.';
answer += target;
chk[target - 'A']++;
i = -1;
}
}
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (arr[i][j] != '.')
return "IMPOSSIBLE";
return answer;
}
|
cs |
|
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
87
88
89
90
91
92
93
94
95
96
97
98
|
#include<iostream>
#include <string>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
struct pos {
int y, x;
};
vector<string> arr;
int N, M;
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
vector< vector<pos> > loc;
bool isalpha(char a) {
if (a == '.' || a == '*')
return false;
return true;
}
bool isBool(int y, int x) {
if (0 <= y && y < N && 0 <= x && x < M)
return true;
return false;
}
bool chk(pos from, pos to) {
for (int i = 0; i < 4; i++) {
int ny = from.y + dy[i];
int nx = from.x + dx[i];
while (isBool(ny,nx)){
if (ny == to.y && nx == to.x)
return true;
if (arr[ny][nx] != '.')
break;
for (int j = ((i+1) % 2); j < 4; j += 2) {
int nny = ny + dy[j];
int nnx = nx + dx[j];
while (isBool(nny,nnx)){
if (nny == to.y && nnx == to.x)
return true;
if (arr[nny][nnx] != '.')
break;
nny += dy[j];
nnx += dx[j];
}
}
ny += dy[i];
nx += dx[i];
}
}
return false;
}
bool Test(string &answer,int Left) {
while (1) {
bool match = false;
for (int i = 0; i < 26; i++) {
if (!loc[i].empty()) {
pos from, to;
char target = i + 'A';
from = loc[i][0];
to = loc[i][1];
if (chk(from, to)) {
arr[from.y][from.x] = '.';
arr[to.y][to.x] = '.';
answer += target;
loc[i].clear();
Left -= 2;
match = true;
break;
}
}
}
if (!match)
break;
}
return (Left == 0);
}
string solution(int m, int n, vector<string> board) {
arr = board; N = m; M = n;
int Left = 0;
loc = vector< vector<pos> >(26);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (isalpha(board[i][j])) {
++Left;
loc[board[i][j] - 'A'].push_back({ i, j });
}
}
}
string answer = "";
if (Test(answer,Left)) {
return answer;
}
return "IMPOSSIBLE";
}
|
cs |
Test함수에 answer,Left를 참조하지않고 풀면 오답이뜬다.
이유는 모르겠음..