-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
질문이 있어요 선생님!
21.04.01 23:21 작성 조회수 102
0
선생님, 안녕하세요?
저는
dfs를 통해서 조합을 각각 만들어내고, (x좌표,y좌표,움직인횟수)
그 조합을 대하여 큐에 넣어준 이후 dfs를 돌렸습니다.
큐에서는 fcfs로 어차피 1을 먼저 만나게 되는 정보로 방문처리해주면 그
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
using namespace std;
int map[51][51];
bool visited[51][51];
int N, M;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
typedef struct node {
int x;
int y;
int cnt = 0;
}Node;
queue<Node>Q;
Node piz[2501];
int pcnt = 0;
int pizza[2501];
int flag = 0;
int mini = 10000;
void BFS() {
int cres = 0;
Node current;
while (!Q.empty()) {
current.x = Q.front().x;
current.y = Q.front().y;
current.cnt = Q.front().cnt;
Q.pop();
//printf("current x : %d y : %d cnt : %d\n\n", current.x, current.y, current.cnt);
if (map[current.x][current.y] == 1) {
cres += current.cnt;
//printf("cres : %d \n\n", cres);
}
else {
for (int i = 0; i < 4; i++) {
int x = current.x + dx[i];
int y = current.y + dy[i];
int c = current.cnt + 1;
if (x >= 1 && y >= 1 && x <= N && y <= N && !visited[x][y] && map[x][y] == 1) {
visited[x][y] = true;
Node next;
next.x = x;
next.y = y;
next.cnt = c;
//printf("next x : %d y :%d cnt : %d\n\n", next.x, next.y, next.cnt);
Q.push(next);
}
if (x >= 1 && y >= 1 && x <= N && y <= N && !visited[x][y] && map[x][y] == 2) {
visited[x][y] = true;
Node next;
next.x = x;
next.y = y;
next.cnt = c;
//printf("next x : %d y :%d cnt : %d\n\n", next.x, next.y, next.cnt);
Q.push(next);
}
if (x >= 1 && y >= 1 && x <= N && y <= N && !visited[x][y] && map[x][y] == 0) {
visited[x][y] = true;
Node next;
next.x = x;
next.y = y;
next.cnt = c;
//printf("next x : %d y :%d cnt : %d\n\n", next.x, next.y, next.cnt);
Q.push(next);
}
}
}
}
if (mini > cres) {
mini = cres;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
visited[i][j] = false;
}
}
}
void DFS(int start, int level) {
if (level == M) {
//printf("<<<start>>>\n\n");
for (int i = 0; i < M; i++) {
visited[piz[pizza[i]].x][piz[pizza[i]].y] = true;
//printf("x : %d y : %d \n\n", piz[pizza[i]].x, piz[pizza[i]].y);
Q.push(piz[pizza[i]]);
}
BFS();
}
else {
for (int i = start; i < pcnt; i++) {
pizza[level] = i;
DFS(i + 1, level + 1);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int input;
cin >> input;
map[i][j] = input;
if (input == 2) {
Node start;
start.x = i;
start.y = j;
start.cnt = 0;
piz[pcnt++] = start;
}
}
}
DFS(0, 0);
printf("%d", mini);
}
이후 중복의 여지도 없을 것이라 생각했구요,
아무튼
1을 만나게 되면 그 때의 이동값을 누적하는 방식으로 해결했씁니다.
아마 이거 백준에 비슷한 문제있었던 거같은데요
이 문제에서는 3번 케이스에서 유일하게 시간 초과가 나는군요ㅜㅜㅜㅜ
어떤 점이 문제일 지 궁금합니다 선생님.ㅜㅜ!
답변을 작성해보세요.
0
답변 1