글 읽기 - 2178번 틀렸습니다.

oookideuk 4년 전 0

astar 알고리즘, 우선순위 큐는 heap을 이용해서 풀어봤는데요.

어디 부분이 잘못됐는지 잘 모르겠습니다.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef struct _Map {
	int h; int w;
	int** map;
}Map;
typedef struct _Start {
	int x; int y;
}Start;
typedef struct _Destination {
	int x; int y;
}Destination;

typedef struct _Node {
	int x;
	int y;
	double f;	// g+h
	double g;	// 출발지점에서 중간지점
	double h;	// 중간지점에서 목표지점
	struct _Node* parent;
	struct _Node* next;
}Node;
typedef struct _Heaptype {
	Node** heap;
	int size;
	int max_size;
}HeapType;

void heap_init(HeapType* h, int height, int width) {
	h->size = 0;
	h->max_size = height * width;
	h->heap = (Node**)malloc(sizeof(Node*) * h->max_size);
}
void heap_insert(HeapType* h, Node *node) {
	int idx;
	idx = ++(h->size);

	while (idx != 1 && (node->f < h->heap[idx / 2]->f)) {
		h->heap[idx] = h->heap[idx / 2];
		idx /= 2;
	}
	h->heap[idx] = node;
}
Node* heap_pop(HeapType* h) {
	Node* ret_node = h->heap[1];
	Node* temp_node = h->heap[h->size];
	h->size--;
	int parent = 1, child = 2;

	while (child <= h->size) {
		if ((child < h->size) && ((h->heap[child]->f) > h->heap[child + 1]->f)) { child++; }
		if (temp_node->f <= h->heap[child]->f) { break; }

		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;	// 왼쪽 자식노드 인덱스가 됨.
	}

	h->heap[parent] = temp_node;

	return ret_node;
}
int heap_search(HeapType* h, int x, int y) {
	for (int i = 1; i <= h->size; i++) {
		if (h->heap[i]->x == x && h->heap[i]->y == y) { return i; }
	}
	return 0;
}
void heap_replace(HeapType* h, Node* node) {
	HeapType temp;
	temp.heap = (Node**)malloc(sizeof(int*) * h->max_size);
	temp.size = 0;
	for (int i = 1; i <= h->size; i++) {
		Node* b = heap_pop(h);
		if (b->x != node->x && b->y != node->y) { heap_insert(&temp, b); }
		else { heap_insert(&temp, node); free(b); }
	}
	
	free(h->heap);
	h->heap = temp.heap;
}

void map_create(Map* map, int h, int w) {
	map->h = h; map->w = w;
	// h * w 크기의 2차원 배열 생성
	int** pmap = (int**)malloc(sizeof(int*) * h);
	if (pmap == NULL) return;
	for (int i = 0; i < h; i++) {
		pmap[i] = (int*)malloc(sizeof(int) * w);
		if (pmap[i] == NULL) return;
	}
	// map에 문자 입력
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			scanf("%1d", &pmap[i][j]);

	map->map = pmap;
}
void free_map(Map* map) {
	int h = map->h;
	for (int i = 0; i < h; i++) {
		free(map->map[i]);
	}
	free(map->map);
}

double get_cost(int srcx, int srcy, int destx, int desty) {
	return sqrt((srcx - destx) * (srcx - destx) + (srcy - desty) * (srcy - desty));
}

Node* astar(Map* pmap, Start start, Destination dest) {
	Node* cur_node = (Node*)malloc(sizeof(Node));
	if (cur_node == NULL) return NULL;
	cur_node->x = start.x; cur_node->y = start.y; cur_node->parent = NULL;
	cur_node->f = 0; cur_node->g = 0; cur_node->h = 0; cur_node->next = NULL;

	HeapType o_list;
	HeapType c_list;
	heap_init(&o_list, pmap->h, pmap->w);
	heap_init(&c_list, pmap->h, pmap->w);

	heap_insert(&c_list, cur_node);	// 1.첫 출발노드를 닫힌 목록에 넣는다.
	while (1) {
		// 탈출조건1: 목적지에 노드에 도착
		if (cur_node->x == dest.x && cur_node->y == dest.y) break;

		// 2. 현재노드의 주변노드를 검색한 후 이동 가능한 노드일 경우 열린목록에 넣는다.
		int x = 0; int y = 0;
		for (int i = -1; i < 2; i++) {
			for (int j = -1; j < 2; j++) {
				x = cur_node->x + i;
				y = cur_node->y + j;
				// map의 범위를 벗어나는 경우 continue 처리
				if (x <= -1 || y <= -1 || x >= pmap->h || y >= pmap->w) { continue; }
				// 이동불가 지역이거나, 주변노드가 c_list에 존재하는 경우 continue 처리
				if (pmap->map[x][y] != 1 || heap_search(&c_list, x, y) > 0) { continue; }
				// 동,서,남,북으로만 움직이기때문에 대각선이동 예외처리
				if (cur_node->x != x && cur_node->y != y) { continue; }

				Node* data = (Node*)malloc(sizeof(Node));
				if (data == NULL) return NULL;
				data->x = x;
				data->y = y;
				data->parent = cur_node;
				data->g = get_cost(data->x, data->y, cur_node->x, cur_node->y) + cur_node->g;	// 주변노드에서 부모노드까지의 cost+ 부모노드g
				data->h = get_cost(data->x, data->y, dest.x, dest.y);	// 주변노드에서 목표노드까지의 cost
				data->f = data->g + data->h;
				data->next = NULL;

				// o_list에 data가 존재하면, o_l에 있는 g와 추가하려는 data의 g를 비교후 작은 것으로 교체, 없으면 그냥 insert
				// g가 변경되면 f가 변경되는데 구현한 우선순위 큐는 리밸런싱이 안되기 때문에 삭제 후 다시 삽입 해야함.
				int idx = heap_search(&o_list, data->x, data->y);
				if (idx > 0) {
					if (o_list.heap[idx]->g > data->g)
						heap_replace(&o_list, data);
				}
				else {
					heap_insert(&o_list, data);
				}
			}
		}
		// 탈출조건2: 열린목록이 비워짐, 탐색가능한 노드가 없음.
		if (o_list.size == 0) { return NULL; }
		
		// 3. 선택된 노드 o_list에서 제거 및 c_list에 추가
		cur_node = heap_pop(&o_list);
		heap_insert(&c_list, cur_node);

	}
	return cur_node;
}

int main(void) {
	Map map;
	Start start; start.x = 0; start.y = 0;
	Destination dest;	// 목표지점
	int h, w;	// 높이, 너비;
	scanf("%d %d", &h, &w);
	dest.x = h - 1; dest.y = w - 1;

	map_create(&map, h, w);

	Node* a = astar(&map, start, dest);
	if (a == NULL) { printf("0\n"); return 0; }

	int count = 0;
	while (a != NULL) {
		//printf("%d,%d \n", a->x, a->y);
		count++;
		a = a->parent;
	}
	printf("%d\n", count);

	free_map(&map);

	return 0;
}

sait2000 4년 전 0

77번 줄에 &&를 ||로 고쳐야 합니다

oookideuk 4년 전 0

&&를 ||로 바꿧더니 말씀하신 케이스는 잘 돌아갑니다.

그래도 제출 했을 때는 틀렸다고 나오네요.

그리고 노드를 열린목록에 넣기전에 열린목록에 중복되는 노드가 있으면 replace함수가 실행되는데요.

열린목록에서 노드를 하나씩 pop해서 입력할 노드와 중복되는 노드를 찾은 다음 cost를 비교해서 더 낮은 cost를 가진 노드만 열린목록에 넣고 있습니다.

이 때 두 노드가 중복 된다는 걸 알려면 x,y좌표가 같아야해서 &&를 써야하는 것 아닌가요?

djm03178 4년 전 0

같다를 판정하려면 둘 다 같아야 합니다.

같지 않다를 판정하려면 둘 중 하나라도 같지 않으면 됩니다.

oookideuk 4년 전 0

자바로 작성하니까 맞았습니다.

아마 heap관련 함수나 포인터가 잘못된거 같아요.

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Pos{
	public int x;
	public int y;
	public Pos(int x, int y){this.x=x; this.y=y;}
	// 중복 확인하기
	@Override
	public boolean equals(Object obj){
		if(obj == null) return false;
		if(obj instanceof Pos){
			Pos c = (Pos)obj;
			return this.x == c.x && this.y == c.y;
		}
		return false;
	}
}

class Node implements Comparable<Node>{
	public Pos pos;
	public double f; // g+h
	public double g; //출발지점에서 중간지점
	public double h; //중간지점에서 목표지점
	public int condition; //0 이동가능, 1 이동불가
	public Node parent;
	
	// 오름차순 정렬
	@Override
	public int compareTo(Node t){
		return this.f < t.f ? -1 : 1;
	}
}

public class Main {
	static int height;
	static int width;
	static int[][] map;
	static Pos dest;
	static Queue<Node> oList = new PriorityQueue<>();
	static List<Node> cList = new ArrayList<Node>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		height = sc.nextInt();
		width = sc.nextInt();	// 개행문자 전까지 입력 받음
		sc.nextLine();	// 개행문자 까지 입력 받음
		dest = new Pos(height-1,width-1);
		map = new int[height][width];
		
		for(int i=0; i<height; i++){
			String str = sc.nextLine();
			for(int j=0; j<width; j++){
				map[i][j] = str.charAt(j)-'0';	// String.charAt(idx) 문자열중 해당 인덱스 문자 추출
			}
		}
		
		Node a = aStar(map);
		int count = 0;
		while(a != null){
			//System.out.println(a.pos.x+","+a.pos.y);
			count++;
			a = a.parent;
		}
		System.out.println(count);
		sc.close();
	}
	
	// 길찾기 수행
	static Node aStar(int[][] map ){
		Node curNode = new Node();
		curNode.pos = new Pos(0,0);
		
		// 1. 첫 출발 노드를 닫힌목록에 넣는다.
		cList.add(curNode);
		while(true){
			// 탈출조건 1: 목적지 노드에 도착
			if(curNode.pos.x == dest.x && curNode.pos.y == dest.y) {break;}
			
			// 2. 현재노드의 주변노드를 검색한 후 이동 가능한 노드일 경우 열린목록에 넣는다.
			int x=0; int y=0;
			for(int i=-1; i<2; i++){
				for(int j=-1; j<2; j++){
					x=curNode.pos.x + i;
					y=curNode.pos.y + j;
					// map의 범위를 벗어나는 경우
					if(x <= -1 || y <= -1 || x >= height || y >= width) {continue;}
					// 이동불가 지역 OR 주변노드가 cList에 존재하는 경우
					if(map[x][y] != 1 || IsPosInCList(new Pos(x,y))) {continue;}
					// 동,서,남,북으로만 움직이기때문에 대각선이동 X
					if (curNode.pos.x != x && curNode.pos.y != y) { continue; }
					
					Node data = new Node();
					data.pos = new Pos(x,y);
					data.g=getCost(data.pos.x,data.pos.y,curNode.pos.x,curNode.pos.y)+curNode.g;
					data.h=getCost(data.pos.x,data.pos.y,dest.x,dest.y);
					data.f=data.g+data.h;
					data.parent=curNode;
					
					// o_list에 data가 존재하면, o_l에 있는 g와 추가하려는 data의 g를 비교후 작은면 교체, 없으면 그냥 insert
					Node temp = findNodeInOpen(data.pos);
					if(temp == null){
						oList.add(data);
					}else{
						if(temp.g > data.g){
							temp.g = data.g;
							temp.parent = data.parent;
						}
					}
				}
			}
			// 탈출조건2: 열린목록이 비워짐, 탐색가능한 노드가 없음.
			if (oList.isEmpty()) { return null; }
			// 3. 열린목록에서 반환한 뒤 닫힌목록에 입력
			curNode = oList.poll();
			cList.add(curNode);
		}
		
		return curNode;
	}
	
	// 닫힌노드에 중복된 노드 존재하는지 확인
	static boolean IsPosInCList(Pos pos){
		if(cList.isEmpty() || pos == null) { return false; }
		for(Node node: cList)
			if(node.pos.equals(pos)) { return true; }
		
		return false;
	}
	// 열린목록에 중복된 노드 존재하는지 확인
	static Node findNodeInOpen(Pos pos)
	{
		if (pos == null || oList.isEmpty()) { return null; }
		for (Node node : oList)
			if (node.pos.equals(pos)) { return node; }
		
		return null;
	}
	
	static double getCost(double srcX, double srcY, double destX, double destY) {
		return Math.sqrt((srcX-destX)*(srcX-destX)+(srcY-destY)*(srcY-destY));
	}
}

oookideuk 4년 전 0

157라인의 중복된 노드 교체하기를 아래 소스 처럼 바꿧더니 통과했습니다.

int idx = heap_search(&o_list, data->x, data->y);
if (idx > 0) {
	if (o_list.heap[idx]->g > data->g)
        //heap_replace(&o_list, data);
		o_list.heap[idx]->g = data->g;
		o_list.heap[idx]->parent = data->parent;
}
else {
	heap_insert(&o_list, data);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2178번 틀렸습니다.

oookideuk 4년 전 0

sait2000 4년 전 0

oookideuk 4년 전 0

djm03178 4년 전 0

oookideuk 4년 전 0

oookideuk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말