queue를 구현해 보자

큐가 뭔지 다 알것이라 생각한다. 바로 코드부터 보자
아 그전에 연결리스트로 구현 할 것이다.

Q. 하... ㅆ ㅣ.. ㅂ......
A. ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!

struct node
{
	int x, y;
	struct node* next;
};
struct node* f, * r;
void push(int, int);
struct node pop();
void push(int x, int y)
{
	struct node* temp;
	temp = (struct node*)malloc(sizeof(struct node));
	temp->x = x;
	temp->y = y;
	temp->next = 0;
	if (!f) // 큐가 비어있다면
	{
		f = temp;
	}
	else // 큐가 비어있지 않다면
	{
		r->next = temp;
	}
	r = temp;
}
struct node pop()
{
	struct node* temp, ret;
	temp = f;
	ret = *f;
	f = f->next;
	free(temp);
	return ret;
}

큐나 스택 구현할때는 난 더미노드 안둔다. init()만들기 귀찬다.

이제 보자
초기상태다 전역변수니 0(NULL) 박혀있다. 그리고 큐가 비어있는 상태이다 이럴떄 push를 보자

라인 하나하나 그림으로 그렸다.(친절한 21씨)
이제 큐가 비었지 않은 상태에서 push해보자

이게 전부다.

이제 이 상태에서 pop을 해보자 코드를 보면 알겠지만 pop은 if문이 없어서 항상 같은짓을 반복한다.

끝

Q. 하.... 님... isempty()정도는 그래도 만들어야죠....
A. f

오늘 내가 이 코드를 검증받기 위해 준비한 문제는 bfs문제이다. bfs를 풀기 위해서는 queue가 필요한데 대부분 stl을 이용해서 구현을 하면

while(!(q.isempy()))
{
.
.
.
}

이런 문구가 들어갈 것이다. 근데 난 isempty() 만들기 귀차나서

while(f)
{
.
.
.
}

이렇게 쓴다.
위의 그림에서 한번더 pop을 해보자

f가 NULL이면 큐가 빈 것이고 f가 NULL이 아니면 큐가 비어있지 안은거다. 그래서 위의 코드가 잘 돌아간다.

Q. 야이 근본없는새끼야 r에다가 NULL박아줘야지
A. 나도 안다. 나도 예전에는 그랬다. 근데 이젠 귀찬타. r변수 안쓰면 그만이다. 너는 그 line적어서 써도 된다. 이게 맘에 안든다면 터트리는 test case만들어 주라. 내가 고칠게.

출처 : https://www.acmicpc.net/problem/17836
근데 코드 짜보고니 bfs가 아니가 다익스트라 인데 좀 애매하네;;
dis1 : 용사 -> 공주
dis2 : 용사 -> 그람 + 그럄 -> 공주
비교해서 답 구하면 된다.

#include<stdio.h>
#include<malloc.h>
#define inf 50000
struct node
{
	int x, y;
	struct node* next;
};
struct point
{
	int x, y;
};
struct node* f, * r;
struct point so, start, end;
int map[100][100], memo[100][100];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int answer, h, w, limit;
void push(int, int);
struct node pop();
int isin(int, int);
void input();
void go();
int calc();
int get_min(int, int);
int get_dis(struct point, struct point);
int get_abs(int, int);
int make_answer();
int main(void)
{
	answer = make_answer();
	if (answer == -1)
	{
		printf("Fail\n");
	}
	else
	{
		printf("%d\n", answer);
	}
	return 0;
}
int make_answer()
{
	int ret;
	input();
	go();
	ret = calc();
	return ret;
}
void input()
{
	int i, j;
	scanf("%d %d %d", &h, &w, &limit);
	for (i = start.x = start.y = 0, end.x = h - 1, end.y = w - 1; i < h; i++)
	{
		for (j = 0; j < w; j++)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2)
			{
				so.x = i;
				so.y = j;
			}
			memo[i][j] = inf;
		}
	}
}
void go()
{
	int d, nx, ny;
	struct node pnode;
	memo[0][0] = 0;
	push(0, 0);
	while (f)
	{
		pnode = pop();
		for (d = 0; d < 4; d++)
		{
			nx = pnode.x + dx[d];
			ny = pnode.y + dy[d];
			if (isin(nx, ny) && map[nx][ny] != 1 && memo[nx][ny] > memo[pnode.x][pnode.y] + 1)
			{
				memo[nx][ny] = memo[pnode.x][pnode.y] + 1;
				push(nx, ny);
			}
		}
	}
}
int calc()
{
	int dis1, dis2, ret;
	dis1 = memo[h - 1][w - 1];
	dis2 = memo[so.x][so.y] + get_dis(so, end);
	ret = get_min(dis1, dis2);
	return ret > limit ? -1 : ret;
}
int get_min(int a, int b)
{
	return a > b ? b : a;
}
void push(int x, int y)
{
	struct node* temp;
	temp = (struct node*)malloc(sizeof(struct node));
	temp->x = x;
	temp->y = y;
	temp->next = 0;
	if (!f)
	{
		f = temp;
	}
	else
	{
		r->next = temp;
	}
	r = temp;
}
struct node pop()
{
	struct node* temp, ret;
	temp = f;
	ret = *f;
	f = f->next;
	free(temp);
	return ret;
}
int isin(int x, int y)
{
	return 0 <= x && x < h && 0 <= y && y < w;
}
int get_dis(struct point a, struct point b)
{
	return get_abs(a.x, b.x) + get_abs(a.y, b.y);
}
int get_abs(int a, int b)
{
	return a > b ? a - b : b - a;
}