주방장은 시각 t에 위치가 x인 의자 앞에 있는 벨트위에 name이름을 부착한 초밥을 올려둠
(단, 같은 위치에 여러 초밥을 올려두어도 OK,
같은 이름의 초밥도 OK)
ii) 손님 입장
시각 t에 회전 벨트가 시계 방향으로 회전한 직후,
이름이 name인 사람이 위치가 x인 의자에 앉는다.
(해당 위치엔 사람이 없다고 가정한다.)
이때 부터, 위치 x 앞으로 오는 초밥들중
자신의 이름이 적혀있는 초밥을 정확히 n개를 먹고 자리를 떠난다.
만약 시각 t에 위치 x에 자신의 이름이 적힌 초밥이 있다면 앉자마자 먹는다.
(여러개가 있다면 여러개 먹는다)
(단, 오는 손님은 모두 다르다 = 재방문이 없다)
Ii) 촬영
시각 t에 회전 벨트가 시계 방향으로 회전한 직후,
이름이 name인 사람이위치 x앞으로 오는 초밥들을 먹고,
상태를 촬영해
남은 사람 수, 초밥 수를 출력한다.
[방법]
초밥을 생성하는 명령(100)만 탐색해
해당 초밥의 소멸시간을 계산함.
모든 사건이 일어난 명령들의 집합에
초밥의 소멸시간을 계산한 집합을
합쳐서
t가 작은 시각부터 사건의 순서에 맞게 집합을 정렬함
그러면 아래와 같은 형태가 완성됨.
합쳐진 집합을 탐색하며
초밥이 생성되면 sushi_cnt += 1
초밥이 사라지면 sushi_cnt -= 1
손님이 방문하면 customer +=1
초밥이 사라지면 누가 먹었는지 확인해 그 사람이 앞으로 먹어야하는 초밥 갯수 -1한 후
앞으로 먹어야하는 초밥 갯수가 0가 되어 손님이 나가면 customer -= 1
[회고]
시간 초과 해결하기위해
for(사람 이름 : 사람 목록) {
for(cmd == 100 : 명령 집합) {
}
}
위와 같은 2중 for문을 구현한다면
사람의 최대 수 15,000명
최대 명령수 100,000로
15,000 x 100,000 = 15억 이므로
시간초과 나기에
분리해주는 작업을 거쳤다.
[코드]
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;
#define FOR(i,s,e) for(int i=s; i<e; ++i)
#define Q_MAX 10
int L, Q;
struct CMD {
int cmd, x, t, n;
string name;
};
vector<CMD> commands;
unordered_map<string, int> sitting_position; // 손님이 앉은 자리 매핑
unordered_set<string> visitting_customer_names; // 방문한 손님 목록 저장 ( 재방문은 없으므로 중복이 없다 )
unordered_map<string, int> visit_customer_time; // 손님이 방문한 시간대
unordered_map<string, int> eat_cnt; // 손님이 먹어야할 초밥 갯수 매핑
vector<CMD> v;
int sushi_cnt; // 남은 초밥 갯수
int customer_cnt; // 남은 손님 명수
void input() {
cin >> L >> Q;
FOR(i, 0, Q) {
int cmd = -1, t = -1, x = -1, n = -1;
string name = "";
cin >> cmd;
if (cmd == 100) {
cin >> t >> x >> name;
}
else if (cmd == 200) {
cin >> t >> x >> name >> n;
visitting_customer_names.insert(name);
sitting_position[name] = x; // 오는 손님은 모두 다르다 ( 재방문 x )
visit_customer_time[name] = t; // 손님이 방문한 시각
eat_cnt[name] = n;
}
else if (cmd == 300) cin >> t;
CMD tmp;
tmp.cmd = cmd;
tmp.t = t;
tmp.x = x;
tmp.name = name;
tmp.n = n;
commands.push_back(tmp);
}
}
bool mcmp(CMD left, CMD right) {
if (left.t > right.t) return false;
if (left.t < right.t) return true;
if (left.cmd > right.cmd) return false;
if (left.cmd < right.cmd) return true;
return false;
}
void sol() {
FOR(i,0, commands.size()) {// 생성된 초밥이 언제 없어질지 기록
if (commands[i].cmd != 100) continue; // 초밥이 생성된 시점이 아니라면 pass
CMD sushis = commands[i];
// 해당 손님(commads[i].name)이 먹어야할 초밥
/*
시간 초과 관리를 위해 초밥생성 관련 명령 분리
최대 명령 수 : 100,000
회대 사람 수 : 15,000
*/
int meet_sushi_cutomer_time = 0; // 초밥과 손님이 만나게 할 수 있는 보정 시간
int eat_sushi_time = 0; //초밥을 먹는 시간
if (sushis.t < visit_customer_time[sushis.name]) {
/*
손님 입장전에 손님의 초밥이 벨트위에 있음
*/
// 현재 초밥의 위치
int now_sushi_position = sushis.x;
// 손님이 방문한 시점과 먹어야할 초밥이 들어온 시점의 차이
int diff_t = visit_customer_time[sushis.name] - sushis.t;
// 손님이 입장했을때, 회전 초밥 위치 이동
//
// 손님이 입장하기 전에 먹어야할 초밥이 들어와있으므로
// 손님이 들어올 시점에 초밥이 어디로 이동할지 구해줌
now_sushi_position = ((now_sushi_position + diff_t) % L);
if (sitting_position[sushis.name] >= now_sushi_position) {
/*
손님이 초밥보다 시계방향으로 더 먼쪽에 앉아 있음
*/
// 손님이 초밥을 먹기위해 걸리는 시간 = 손님이 앉은 자리 위치 - 현재 초밥 위치
meet_sushi_cutomer_time = sitting_position[sushis.name] - now_sushi_position;
}
else if (sitting_position[sushis.name] < now_sushi_position) {
/*
손님이 초밥보다 반시계방향으로 더 먼쪽에 앉아 있음
*/
// 손님이 초밥을 먹기위해 걸리는 시간 = (손님이 앉은 자리 위치 + 의자의 갯수(1싸이클)) - 현재 초밥 위치
meet_sushi_cutomer_time = (sitting_position[sushis.name] + L) - now_sushi_position;
}
// 손님을 초밥을 먹을 수 있는 시간 = 손님이 방문한 시간대 + 손님이 초밥을 먹기위해 걸리는 시간
eat_sushi_time = visit_customer_time[sushis.name] + meet_sushi_cutomer_time;
}
else {
/*
손님 입장 후 초밥이 벨트위로 올라옴
*/
// 현재 초밥의 위치
int now_sushi_position = sushis.x;
if (sitting_position[sushis.name] >= now_sushi_position) {
/*
손님이 초밥보다 시계방향으로 더 먼쪽에 앉아 있음
*/
// 손님이 초밥을 먹기위해 걸리는 시간 = 손님이 앉은 자리 위치 - 현재 초밥 위치
meet_sushi_cutomer_time = sitting_position[sushis.name] - now_sushi_position;
}
else if (sitting_position[sushis.name] < now_sushi_position) {
/*
손님이 초밥보다 반시계방향으로 더 먼쪽에 앉아 있음
*/
// 손님이 초밥을 먹기위해 걸리는 시간 = (손님이 앉은 자리 위치 + 의자의 갯수(1싸이클)) - 현재 초밥 위치
meet_sushi_cutomer_time = (sitting_position[sushis.name] + L) - now_sushi_position;
}
// 손님을 초밥을 먹을 수 있는 시간 = 초밥이 들어온 시간 + 손님이 초밥을 먹기위해 걸리는 시간
eat_sushi_time = sushis.t + meet_sushi_cutomer_time;
}
// 초밥이 사라지는 시점을 저장
CMD tmp;
tmp.cmd = sushis.cmd + 1;
tmp.t = eat_sushi_time;
tmp.x = -1;
tmp.name = sushis.name;
tmp.n = -1;
v.push_back(tmp);
}
// 전체 명령과 초밥이 사라지는 시점에 대한 정보를 합침
commands.insert(commands.end(), v.begin(), v.end());
// t가 작을 수록, 명령이 작을수록 우선순위를 부여해 정렬함
// 명령 우선순위 (100 -> 101 -> 200 -> 300)
sort(commands.begin(), commands.end(), mcmp);
FOR(i, 0, commands.size()) {
/*
전체 명령과 초밥이 사라지는 시점에 대한 정보를 합친것을 바탕으로
cmd에 따른 작업을 수행
*/
if (commands[i].cmd == 100) {
/*
초밥이 생성됨
*/
++sushi_cnt;
}
else if (commands[i].cmd == 101) {
/*
초밥이 사라짐
*/
--sushi_cnt;
// 초밥이 사라졌으므로 손님을 먹을 초밥 갯수를 줄임
string now_name = commands[i].name;
eat_cnt[now_name] = eat_cnt[now_name] - 1;
if (eat_cnt[now_name] <= 0) --customer_cnt; // 손님이 먹을 초밥의 갯수가 0이하가 되었다면 방문한 손님 수는 줄어듬
}
else if (commands[i].cmd == 200) {
/*
손님이 방문함
*/
++customer_cnt;
}
else if (commands[i].cmd == 300) {
/*
촬영
*/
cout << customer_cnt << " " << sushi_cnt << '\n';
}
}
}
int main() {
// 여기에 코드를 작성해주세요.
freopen("input.txt", "r", stdin);
input();
sol();
return 0;
}
각 기사가 "이동한 위치"에서 (r,c) 좌상단을 기준으로 h x w의 영역 내에 함정 수만큼 피해를 입음
if ( 현재체력 < 피해 입을 체력 ) 기사는 체스판에서 사라짐
[방법]
for ( 왕의 명령 수만큼 반복 )
if ( 기사가 체스판위에 아직 있는지 확인 ) 없다면 pass
기사 위치를 백업 (knigh_map) // (tmp_knight_map 을 활용해 기사 이동 가능여부 판단)
if ( 이동할 수 있는지(기사번호, 이동방향) ) 이동할 수 없다면 pass
기사 위치 갱신 (tmp_knight_map -> knight_map)
기사 정보(좌표, 피해량) 갱신
이동할 수 있는지 판단하는 함수를 재귀호출로 구현.
왕의 명령 -> 해당 기사의 이동 가능 여부 판단 -> 다른 기사가 있다면 -> 다른 기사의 이동 가능 여부 판단 -> ...
왕의 명령 -> 해당 기사의이동 가능 여부 판단-> 벽이 있다면 -> 재귀를 빠져나옴
[설명]
can_move_knight(기사 번호, 이동 방향)
기사의 이동 가능여부를 판단하고
이동이 가능한 기사에 한해 기사 이동
bool can_move_knight(int num, int dir) { // 기사번호, 방향
KNIGHT* now = &knights[num];
int ny = now->r + dy[dir];
int nx = now->c + dx[dir];
if ((ny < 1) || ((ny + now->h - 1) > L) || (nx < 1) || ((nx + now->w - 1) > L)) return false; // 영역을 벗어남
FOR(y, ny, (ny + now->h)) {
FOR(x, nx, (nx + now->w)) {
if (map[y][x] == 2) return false; // 벽에 막힘
}
}
FOR(y, ny, (ny + now->h)) {
FOR(x, nx, (nx + now->w)) {
if ((knight_map[y][x] != 0) && (knight_map[y][x] != num)) { // 자신이 아닌 다른 기사가 있음
if (can_move_knight(knight_map[y][x], dir) == false) return false; // 다른 기사가 이동 못함
}
}
}
move_knight(num, dir); // 기사 이동
return true;
}
update_knight_info(기사 번호)
기사가 이동한 위치, 피해량 갱신
void update_knight_info(int num) {
bool visit[KNIGHTS_MAX] = { 0, };
FOR(y, 1, (L + 1)) { // 좌표 갱신
FOR(x, 1, (L + 1)) {
int now = knight_map[y][x];
if (now == 0) continue;
if (visit[now] == true) continue;
visit[now] = true;
if (knights[now].k <= 0) continue; // 이미 체스판에서 사라진 기사
if (knights[now].r != y || knights[now].c != x) knights[now].isMove = true; // 기사의 이동여부 플래그처리
knights[now].r = y;
knights[now].c = x;
}
}
FOR(i, 1, (N + 1)) { // 피해계산
KNIGHT* now = &knights[i];
if (now->isMove == false) continue; // 이동한적 없는 기사라면
now->isMove = false;
if (i == num) continue; // 명령받은 기사
if (now->k <= 0) continue; // 이미 체스판에서 사라진 기사
int trap_cnt = 0;
FOR(y, now->r, (now->r + now->h)) {
FOR(x, now->c, (now->c + now->w)) {
if (map[y][x] == 1) ++trap_cnt;
}
}
now->k -= trap_cnt;
now->damage_sum += trap_cnt;
if (now->k <= 0) { // 체력이 0이하가 되면 체스판에서 사라짐
FOR(y, now->r, (now->r + now->h)) {
FOR(x, now->c, (now->c + now->w)) {
knight_map[y][x] = 0;
}
}
}
}
}
isMove변수로 이동여부를 확인해 이동했던 기사인지 확인하고 isMove를 다시 false로 초기화해주었었습니다.
if (i == num) continue; // 명령받은 기사
if (now->k <= 0) continue; // 이미 체스판에서 사라진 기사
if (now->isMove == false) continue; // 이동한적 없는 기사라면
now->isMove = false;
이렇게 처리하니
선행조건에서 판별되어버려
이전의 기록이 초기화되지 않은채 다음 로직으로 넘어가 발생하는 문제였습니다.
그래서 조건의 판별 순서를 바꿔
isMove변수로 이동여부를 확인해 이동했던 기사인지 확인하고 isMove를 다시 false로 초기화 한 후,
왕의 명령을 받은 기사인지, 체스판에서 사라진 기사인지 판별해 주었습니다.
참고) 전체코드 중 Line number (118 ~ 121)
if (now->isMove == false) continue; // 이동한적 없는 기사라면
now->isMove = false;
if (i == num) continue; // 명령받은 기사
if (now->k <= 0) continue; // 이미 체스판에서 사라진 기사
[코드]
#include <iostream>
#include <cstring>
using namespace std;
#define FOR(i,s,e) for(int i=s; i<e; ++i)
#define L_MAX (40 + 1)
#define KNIGHTS_MAX (30 + 1)
#define KING_CMD_NUM 100
int L, N, Q;
int map[L_MAX][L_MAX]; // 지도 ( 0: 빈칸, 1: 함정, 2: 벽 )
int knight_map[L_MAX][L_MAX]; // 기사배치
int tmp_knight_map[L_MAX][L_MAX]; // 기사위치를 백업해둘 변수
struct KNIGHT {
int r, c, h, w, k;
int damage_sum; // 피해의 합을 기록
bool isMove; // 기사가 해당 턴에 밀렸었는지 기록
};
KNIGHT knights[KNIGHTS_MAX]; // 기사들의 정보 저장
struct KING {
int i, d;
};
KING commands[KING_CMD_NUM]; // 왕의 명령들 저장
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void input() {
cin >> L >> N >> Q;
FOR(y, 1, (L + 1)) {
FOR(x, 1, (L + 1)) {
cin >> map[y][x];
}
}
FOR(i, 1, (N + 1)) {
KNIGHT* now = &knights[i];
cin >> now->r >> now->c >> now->h >> now->w >> now->k;
FOR(y, now->r, (now->r + now->h)) {
FOR(x, now->c, (now->c + now->w)) {
knight_map[y][x] = i;
}
}
}
FOR(i, 0, Q) {
KING* now = &commands[i];
cin >> now->i >> now->d;
}
}
void move_knight(int num, int dir) {
KNIGHT* now = &knights[num];
int ny = now->r + dy[dir];
int nx = now->c + dx[dir];
FOR(y, now->r, (now->r + now->h)) {
FOR(x, now->c, (now->c + now->w)) {
if (tmp_knight_map[y][x] == num) {
tmp_knight_map[y][x] = 0;
}
}
}
FOR(y, ny, (ny + now->h)) {
FOR(x, nx, (nx + now->w)) {
if (tmp_knight_map[y][x] == 0) {
tmp_knight_map[y][x] = num;
}
}
}
}
bool can_move_knight(int num, int dir) { // 기사번호, 방향
KNIGHT* now = &knights[num];
int ny = now->r + dy[dir];
int nx = now->c + dx[dir];
if ((ny < 1) || ((ny + now->h - 1) > L) || (nx < 1) || ((nx + now->w - 1) > L)) return false; // 영역을 벗어남
FOR(y, ny, (ny + now->h)) {
FOR(x, nx, (nx + now->w)) {
if (map[y][x] == 2) return false; // 벽에 막힘
}
}
FOR(y, ny, (ny + now->h)) {
FOR(x, nx, (nx + now->w)) {
if ((knight_map[y][x] != 0) && (knight_map[y][x] != num)) { // 자신이 아닌 다른 기사가 있음
if (can_move_knight(knight_map[y][x], dir) == false) return false; // 다른 기사가 이동 못함
}
}
}
move_knight(num, dir); // 기사 이동
return true;
}
void update_knight_info(int num) {
bool visit[KNIGHTS_MAX] = { 0, };
FOR(y, 1, (L + 1)) { // 좌표 갱신
FOR(x, 1, (L + 1)) {
int now = knight_map[y][x];
if (now == 0) continue;
if (visit[now] == true) continue;
visit[now] = true;
if (knights[now].k <= 0) continue; // 이미 체스판에서 사라진 기사
if (knights[now].r != y || knights[now].c != x) knights[now].isMove = true; // 기사의 이동여부 플래그처리
knights[now].r = y;
knights[now].c = x;
}
}
FOR(i, 1, (N + 1)) { // 피해계산
KNIGHT* now = &knights[i];
if (now->isMove == false) continue; // 이동한적 없는 기사라면
now->isMove = false;
if (i == num) continue; // 명령받은 기사
if (now->k <= 0) continue; // 이미 체스판에서 사라진 기사
int trap_cnt = 0;
FOR(y, now->r, (now->r + now->h)) {
FOR(x, now->c, (now->c + now->w)) {
if (map[y][x] == 1) ++trap_cnt;
}
}
now->k -= trap_cnt;
now->damage_sum += trap_cnt;
if (now->k <= 0) { // 체력이 0이하가 되면 체스판에서 사라짐
FOR(y, now->r, (now->r + now->h)) {
FOR(x, now->c, (now->c + now->w)) {
knight_map[y][x] = 0;
}
}
}
}
}
void sol() {
FOR(cmd_num, 0, Q) {
if (knights[commands[cmd_num].i].k <= 0) continue; // 체스판에서 사라진 기사
memcpy(tmp_knight_map, knight_map, sizeof(knight_map)); // 백업
if (can_move_knight(commands[cmd_num].i, commands[cmd_num].d) == false) {
continue; // 명령 받은 기사가 움직일 수 있는지
}
memcpy(knight_map, tmp_knight_map, sizeof(knight_map)); // 갱신
update_knight_info(commands[cmd_num].i);
}
int ans = 0;
FOR(i, 1, (N + 1)) {
KNIGHT* now = &knights[i];
if (now->k <= 0) continue;
ans += now->damage_sum;
}
cout << ans;
}
int main() {
// 여기에 코드를 작성해주세요.
freopen("input.txt", "r", stdin);
input();
sol();
return 0;
}
int dy[5] = { 0,0,0,-1,1 }; // 동 서 북 남 int dx[5] = { 0,1,-1,0,0 };
를 사용했습니다.
위 그림처럼 온풍기의 바람 방향이 동쪽(1)일 때,
방향벡터 배열 1~4까지 탐색하면서
① 동쪽(1)일 때,
동쪽(1) 방향으로 벽의 유무를 확인한 뒤
벽이 없다면 이동하고
② 서쪽(2)은 지나치고
③ 북쪽(3)이나 남쪽(4)일 때,
위, 아래에 벽의 유무를 확인한 뒤
벽이 없다면 이동하고
동쪽(1)의 벽의 유무를 확인한 뒤
벽이 없다면 이동하도록
구현했습니다.
벽 위치 저장
map배열 좌표에 근거해
(r, c, d) = {(5, 4, 0), (4, 4, 1), (5, 6, 0)}
입력을 받는다면,
벽의 위치는 wall배열에 따르면
(r, c) = {(8, 7), (7,8), (8,11)}
에 저장되어 있게 됩니다.
따라서,
map배열에서 r좌표가 x이라면
wall배열에서 r좌표는 (x * 2) -1 임이 성립됩니다.
map배열 좌표에서 r좌표가 x, x+1인
사이의 벽은
wall배열에서 (x * 2)임이 성립됩니다.
이를 가정하고 wall 배열을 생성시,
map 배열 크기의 2배만큼 키워
벽의 좌표를 저장했습니다.
[설명]
blow_from_heater(온풍기 인덱스)
주사위를 이동시켰을 때,
주사위의 좌표, 방향, 전개도, 획득한 점수 등을
업데이트해주는 함수
void blow_from_heater(int num) {
/*
온풍기에서 바람이 분다.
*/
queue<pair<int, int>> q; // 탐색할 좌표를 순서대로 집어 넣음
int heater_map[R_MAX][C_MAX] = { 0, }; // 바람이 불면서 몇도의 온도가 저장되는지 기록
int used[R_MAX][C_MAX] = { 0, }; // 이미 바람이 지나갔는지 확인
NODE* now_heater = &heater[num]; // heater배열에서 현재 온풍기에 대한 정보를 저장해둠
// 온풍기에서 바람이 불기 시작하는 위치
int sy = now_heater->y + dy[now_heater->d];
int sx = now_heater->x + dx[now_heater->d];
heater_map[sy][sx] = 5;
used[sy][sx] = 1;
q.push(make_pair(sy, sx));
while (!q.empty()) {
pair<int, int> now = q.front();
q.pop();
FOR(i, 1, 5) {
if (now_heater->d == 1 && i == 2) continue; // 온풍기 방향이 동쪽이면 서쪽은 탐색안함
else if (now_heater->d == 2 && i == 1) continue; // 온풍기 방향이 서쪽이면 동쪽은 탐색안함
else if (now_heater->d == 3 && i == 4) continue; // 온풍기 방향이 북쪽이면 남쪽은 탐색안함
else if (now_heater->d == 4 && i == 3) continue; // 온풍기 방향이 남쪽이면 북쪽은 탐색안함
// 현재 위치에 대한 벽의 유무를 파악
int ty = (now.first * 2) - 1 + dy[i];
int tx = (now.second * 2) - 1 + dx[i];
if (ty < 1 || ty >((R * 2) - 1) || tx < 1 || tx >((C * 2) - 1)) continue; // 범위를 벗어난 벽을 탐색하지 않는지 확인
if (wall[ty][tx] == 1) continue; // 벽에 막혔다면 탐색안함
// 다음 바람이 불 다음 위치 업데이트
int ny = now.first + dy[i];
int nx = now.second + dx[i];
if (i != now_heater->d) {
/*
북쪽이나 남쪽이라면 바람이 불던 방향(동 or 서)으로 한번더 꺽어줘야함
동쪽이나 서쪽이라면 바람이 불던 방향(북 or 남)으로 한번더 꺽어줘야함
*/
// 현재 위치에 대한 벽의 유무파악
ty = (ny * 2) - 1 + dy[now_heater->d];
tx = (nx * 2) - 1 + dx[now_heater->d];
if (ty < 1 || ty >((R * 2) - 1) || tx < 1 || tx >((C * 2) - 1)) continue; // 범위를 벗어난 벽을 탐색하지 않는지 확인
if (wall[ty][tx] == 1) continue; // 벽에 막혔다면
// 다음 바람이 불 다음 위치 업데이트
ny = ny + dy[now_heater->d];
nx = nx + dx[now_heater->d];
}
if (ny < 1 || ny > R || nx < 1 || nx > C) continue; //맵 밖으로 바람이 불진 않는지 확인
if (heater_map[ny][nx] != 0) continue; // 이미 바람이 불었던 위치가 아닌지 확인
if (used[ny][nx] != 0) continue; // 이미 바람이 불었던 위치가 아닌지 확인
if ((heater_map[now.first][now.second] - 1) < 1) continue; // 온도가 0이하라면 더이상 바람이 닿지 않음
heater_map[ny][nx] = heater_map[now.first][now.second] - 1; // 다음 바람이 불 위치의 온도를 저장
used[ny][nx] = 1; // 바람이 지나간 자리임을 표시
q.push(make_pair(ny, nx));
}
}
add_heaterMap_to_temper(heater_map);
}
void move_dice() {
/*
주사위를 이동시켰을 때,
주사위의 좌표, 방향, 전개도, 획득한 점수 등을
업데이트 해주는 함수
*/
if (isMove() == false) {
// 주사위가 이동할 수 없는 방향이라면 반대 방향으로 바꿔줌
if (dice.dir == 0) dice.dir = 2;
else if (dice.dir == 2) dice.dir = 0;
else if (dice.dir == 1) dice.dir = 3;
else if (dice.dir == 3) dice.dir = 1;
}
// 주사위가 이동한 좌표 업데이트
dice.y = dice.y + dy[dice.dir];
dice.x = dice.x + dx[dice.dir];
// 주사위를 굴렸을 때 바뀐 전개도 업데이트
roll_dice();
// 주사위가 획득한 점수 계산
int s = bfs();
score += (map[dice.y][dice.x] * s);
// A는 주사위의 '아랫면'의 눈의 값을 저장
// B는 지도상에서 주사위가 이동한 위치의 정수 값
int A = dice.dice_num[3][1];
int B = map[dice.y][dice.x];
if (A > B) { // A > B 라면 시계 방향으로 90도 회전
dice.dir += 1;
if (dice.dir >= 4) dice.dir = 0;
}
else if (A < B) { // A < B 라면 반시계 방향으로 90도 회전
dice.dir -= 1;
if (dice.dir < 0) dice.dir = 3;
}
}
isMove()
주사위가 이미 지정된 방향으로
이동이 가능한지 여부를 확인하는 함수
bool isMove() {
/*
주사위가 설정한 방향으로 이동이 가능한지 확인
가능하다면 true
불가능하다면 false
*/
int ny = dice.y + dy[dice.dir];
int nx = dice.x + dx[dice.dir];
if (ny < 1 || ny > N || nx < 1 || nx > M) return false;
return true;
}
int bfs() {
/*
지도상에서 주사위가 이동한 위치의 정수 값과
동서남북으로 인접한 좌표에 일치하는 값이 있는지 탐색
val은 지도상에서 주사위가 이동한 위치의 정수 값 저장
cnt는 동일한 값이 인접한 좌표에 몇개가 존재하는지 찾음
*/
queue<pair<int, int>> q;
int used[N_MAX][M_MAX] = { 0, };
int val = map[dice.y][dice.x];
int cnt = 1;
q.push(make_pair(dice.y, dice.x));
used[dice.y][dice.x] = 1;
while (!q.empty()) {
pair<int, int> now = q.front();
q.pop();
FOR(i, 0, 4) {
int ny = now.first + dy[i];
int nx = now.second + dx[i];
if (ny<1 || ny>N || nx<1 || nx>M) continue;
if (used[ny][nx] == 1) continue;
if (map[ny][nx] != val)continue;
used[ny][nx] = 1;
++cnt;
q.push(make_pair(ny, nx));
}
}
return cnt;
}
[코드]
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define N_MAX 20 + 1
#define M_MAX 20 + 1
#define FOR(i,s,e) for(int i=s; i<e; ++i)
struct DICE { // 주사위의 정보를 담은 구조체
int y;
int x;
int dir;
vector<vector<int>> dice_num{ // 주사위 전개도
{0, 2, 0, 0},
{ 4,1,3,6 },
{ 0,5,0,0 },
{ 0,6,0,0 }
};
};
int N, M, K;
int map[N_MAX][M_MAX];
int dy[4] = { 0,1,0,-1 }; // 동 남 북 서
int dx[4] = { 1,0,-1,0 };
DICE dice;
int score;
void init_dice() {
dice.y = 1;
dice.x = 1;
dice.dir = 0; // 시작은 동쪽
}
bool isMove() {
/*
주사위가 설정한 방향으로 이동이 가능한지 확인
가능하다면 true
불가능하다면 false
*/
int ny = dice.y + dy[dice.dir];
int nx = dice.x + dx[dice.dir];
if (ny < 1 || ny > N || nx < 1 || nx > M) return false;
return true;
}
void roll_dice() {
if (dice.dir == 0 || dice.dir == 2) {
if (dice.dir == 0) { // 주사위를 동쪽으로 굴린다.
vector<int> tmp = dice.dice_num[1];
tmp = { tmp[3], tmp[0], tmp[1], tmp[2] };
dice.dice_num[1] = tmp;
}
else if (dice.dir == 2) { // 주사위를 서쪽으로 굴린다.
vector<int> tmp = dice.dice_num[1];
tmp = { tmp[1], tmp[2], tmp[3], tmp[0] };
dice.dice_num[1] = tmp;
}
dice.dice_num[3][1] = dice.dice_num[1][3]; // 주사위 전개도상 '아랫면'에 해당하는 부분 업데이트
}
else if (dice.dir == 1 || dice.dir == 3) {
if (dice.dir == 1) { // 주사위를 남쪽으로 굴린다.
vector<int> tmp = { dice.dice_num[0][1], dice.dice_num[1][1], dice.dice_num[2][1], dice.dice_num[3][1] };
tmp = { tmp[3], tmp[0], tmp[1], tmp[2] };
dice.dice_num[0][1] = tmp[0];
dice.dice_num[1][1] = tmp[1];
dice.dice_num[2][1] = tmp[2];
dice.dice_num[3][1] = tmp[3];
}
else if (dice.dir == 3) { // 주사위를 북쪽으로 굴린다.
vector<int> tmp = { dice.dice_num[0][1], dice.dice_num[1][1], dice.dice_num[2][1], dice.dice_num[3][1] };
tmp = { tmp[1], tmp[2], tmp[3], tmp[0] };
dice.dice_num[0][1] = tmp[0];
dice.dice_num[1][1] = tmp[1];
dice.dice_num[2][1] = tmp[2];
dice.dice_num[3][1] = tmp[3];
}
dice.dice_num[1][3] = dice.dice_num[3][1]; // 주사위 전개도상 '아랫면'에 해당하는 부분 업데이트
}
}
int bfs() {
/*
지도상에서 주사위가 이동한 위치의 정수 값과
동서남북으로 인접한 좌표에 일치하는 값이 있는지 탐색
val은 지도상에서 주사위가 이동한 위치의 정수 값 저장
cnt는 동일한 값이 인접한 좌표에 몇개가 존재하는지 찾음
*/
queue<pair<int, int>> q;
int used[N_MAX][M_MAX] = { 0, };
int val = map[dice.y][dice.x];
int cnt = 1;
q.push(make_pair(dice.y, dice.x));
used[dice.y][dice.x] = 1;
while (!q.empty()) {
pair<int, int> now = q.front();
q.pop();
FOR(i, 0, 4) {
int ny = now.first + dy[i];
int nx = now.second + dx[i];
if (ny<1 || ny>N || nx<1 || nx>M) continue;
if (used[ny][nx] == 1) continue;
if (map[ny][nx] != val)continue;
used[ny][nx] = 1;
++cnt;
q.push(make_pair(ny, nx));
}
}
return cnt;
}
void move_dice() {
/*
주사위를 이동시켰을 때,
주사위의 좌표, 방향, 전개도, 획득한 점수 등을
업데이트 해주는 함수
*/
if (isMove() == false) {
// 주사위가 이동할 수 없는 방향이라면 반대 방향으로 바꿔줌
if (dice.dir == 0) dice.dir = 2;
else if (dice.dir == 2) dice.dir = 0;
else if (dice.dir == 1) dice.dir = 3;
else if (dice.dir == 3) dice.dir = 1;
}
// 주사위가 이동한 좌표 업데이트
dice.y = dice.y + dy[dice.dir];
dice.x = dice.x + dx[dice.dir];
// 주사위를 굴렸을 때 바뀐 전개도 업데이트
roll_dice();
// 주사위가 획득한 점수 계산
int s = bfs();
score += (map[dice.y][dice.x] * s);
// A는 주사위의 '아랫면'의 눈의 값을 저장
// B는 지도상에서 주사위가 이동한 위치의 정수 값
int A = dice.dice_num[3][1];
int B = map[dice.y][dice.x];
if (A > B) { // A > B 라면 시계 방향으로 90도 회전
dice.dir += 1;
if (dice.dir >= 4) dice.dir = 0;
}
else if (A < B) { // A < B 라면 반시계 방향으로 90도 회전
dice.dir -= 1;
if (dice.dir < 0) dice.dir = 3;
}
}
void sol() {
init_dice();
FOR(i, 0, K) {
move_dice();
}
cout << score;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
cin >> N >> M >> K;
FOR(y, 1, (N + 1)) {
FOR(x, 1, (M + 1)) {
cin >> map[y][x];
}
}
sol();
return 0;
}
//-----------------------------------------------------
// 중복 제거 처리
// 중복을 제거하기 위한 정렬을 한다.
sort(ans.begin(), ans.end());
// unique()는 중복된 값을 vector의 가장 뒤로 보내고
// 이러한 값을 보낸 시작 위치를 반환한다.
// erase()를 사용해 중복값이 존재하는 위치부터 끝까지 지워준다.
ans.erase(unique(ans.begin(), ans.end()),ans.end());
//-----------------------------------------------------
중복을 제거하기 위해 unique()를 사용합니다.
다만,
정렬되지 않은 vector에 대해 unique를 적용한다면 아무런 변화가 없습니다.
그렇기에
unique()를 적용하기 전에 vector를 먼저 정렬해주고
unique()를 적용하면 중복값이 제거되.....
.....
.....
지 않습니다.
그 이유는 중복값을 vector의 끝 부분에 보냈을 뿐
vector 끝 부분에 존재하기 때문입니다.
또한 unique()는 중복값을 보낸 시작위치를 가르킵니다.
그래서,
erase()함수를 통해 unique()가 가르킨 위치부터
마지막까지 지워주면
깔끔하게 중복값은 제거됩니다.
[코드]
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define N_MAX 10000000
#define FOR(i,s,e) for(int i=s; i<e; ++i)
vector<int> v;
bool arr[N_MAX];
int num;
vector<int> ans;
vector<int> used;
void dfs(int max_lv, int lv, int n) {
if (max_lv == lv) {
if (arr[n] == true) ans.push_back(n);
return;
}
FOR(i, 0, v.size()) {
if (used[i] == 1) continue;
used[i] = 1;
n = (n * 10) + v[i];
dfs(max_lv, lv + 1, n);
n = (n / 10);
used[i] = 0;
}
}
int solution(string numbers) {
int answer = 0;
//-----------------------------------------------------
//문자열에서 각 숫자 카드를 '한장 씩' 추출
FOR(i, 0, numbers.length()) {
v.push_back(int(numbers[i] - '0'));
}
//-----------------------------------------------------
//-----------------------------------------------------
//가장 큰 수를 확인하기 위해 내림차순으로 정렬
sort(v.begin(), v.end(), greater<int>());
// num변수에 가장 큰 수 저장
FOR(i, 0, v.size()) {
num = (num * 10) + v[i];
}
//-----------------------------------------------------
//-----------------------------------------------------
// 소수확인 후 판별하기 위한 arr배열 초기화
// 소수라면 true, 아니라면 false
memset(arr, true, sizeof(arr));
// 0과 1은 소수가 아니다.
arr[0] = false;
arr[1] = false;
// 가장 큰 수 9999999이므로 배열의 크기는 10000000
// 카드 조합 중 나올 수 있는 가장 큰 수(num)까지 소수 판별을 한다.
FOR(i, 1, 10000000) {
if (arr[i] == false) continue;
int s = i;
for (int j = i * 2; j <= num; j += i) {
arr[j] = false;
}
}
//-----------------------------------------------------
//-----------------------------------------------------
// 카드를 조합해 나올 수 있는 모든 수를 구한다.
FOR(i, 1, v.size() + 1) {
used = vector<int>(v.size(), 0);
dfs(i, 0, 0);
}
//-----------------------------------------------------
//-----------------------------------------------------
// 중복 제거 처리
// 중복을 제거하기 위한 정렬을 한다.
sort(ans.begin(), ans.end());
// unique()는 중복된 값을 vector의 가장 뒤로 보내고
// 이러한 값을 보낸 시작 위치를 반환한다.
// erase()를 사용해 중복값이 존재하는 위치부터 끝까지 지워준다.
ans.erase(unique(ans.begin(), ans.end()),ans.end());
//-----------------------------------------------------
answer = ans.size();
return answer;
}
