글 읽기 - 링크드리스트로 구현하면 시간초과가 뜨네요...

changu02 7년 전 0

나이브하게 하기보단 링크드리스트들을 구현해서 따로 2차원 배열을 선언해주지않고 그냥 좌표값만 받아서 하려했는데

답은 맞는데 시간초과가 뜨네요. 아무래도 배열에 직접 접근하는것이 링크드리스트를 iteration 하는것보다 훨씬 빠른것 같네요.

#include <iostream>
#include <fstream>
using namespace std;
class node{
public:
	node *down = NULL;
	node *next = NULL;
	int xcor;
	int ycor;
};
int repeat = 0;
void mergelist(node *n,node *temp,node *temphead);

int main()
{
	int inputnum;
	int changed = 1;
	cin >> inputnum;
	for (int i = 0; i < inputnum; i++)
	{
		int M, N, K;
		cin >> M >> N >> K;
		node *n=new node;
		for (int i = 0; i < K; i++)
		{
			int r, c;
			cin >> r >> c;
			if (i == 0)
			{
				n->xcor = r;
				n->ycor = c;
				continue;
			}
			node *temp =n;
			while (temp != NULL)
			{
				node *head = temp;
				while (temp != NULL)
				{
					if (r == (temp->xcor + 1) && c == (temp->ycor))
					{
						node *temp2=new node;
						
						temp2->xcor = r;
						temp2->ycor = c;
						temp2->down = temp->down;
						temp->down = temp2;
						node *t = n;
						while (t != NULL )
						{
							if (t == head)
							{
								t = t->next;
								continue;
							}
							mergelist(t, temp2,head);
							t = t->next;
						}
						changed = 0;
						break;
					}
					else if (r == (temp->xcor) && c == (temp->ycor + 1))
					{
						node *temp2=new node;
						
						temp2->xcor = r;
						temp2->ycor = c;
						temp2->down = temp->down;
						temp->down = temp2;
						node *t = n;
						while (t != NULL)
						{
							if (t == head)
							{
								t = t->next;
								continue;
							}
							mergelist(t, temp2,head);
							t = t->next;
						}
						changed = 0;
						break;
					}
					else if (r == (temp->xcor) && c == (temp->ycor - 1))
					{
						node *temp2=new node;
						
						temp2->xcor = r;
						temp2->ycor = c;
						temp2->down = temp->down;
						temp->down = temp2;
						node *t = n;
						while (t != NULL)
						{
							if (t == head)
							{
								t = t->next;
								continue;
							}
							mergelist(t, temp2,head);
							t = t->next;
						}
						changed = 0;
						break;
					}
					else if (r == (temp->xcor - 1) && c == (temp->ycor))
					{
						node *temp2=new node;
		
						temp2->xcor = r;
						temp2->ycor = c;
						temp2->down = temp->down;
						temp->down = temp2;
						node *t = n;
						while (t != NULL)
						{
							if (t == head)
							{
								t = t->next;
								continue;
							}
							mergelist(t, temp2,head);
							t = t->next;
						}
						changed = 0;
						break;
					}
					temp = temp->down;
				}
				temp = head;
				if (changed == 0)
				{
					changed = 1;
					break;
				}
				if (changed == 1 && (temp->next == NULL))
				{
					temp->next = new node;
					temp->next->xcor = r;
					temp->next->ycor = c;
					break;
				}
				temp = temp->next;
				changed = 1;
				
			}
		}
		int m=0;
		while (1)
		{
			if (n->next== NULL)
			{
				break;
			}
			m++;
			n = n->next;
		}
		cout << m+1-repeat << endl;
		repeat = 0;
	}

	return 0;
}

void mergelist(node *n, node *temp, node *temphead)
{
	node *head = n;
	while (n != NULL)
	{
		if (temp->xcor == (n->xcor + 1) && temp->ycor == (n->ycor)&& n!=temp)
		{
			node *tnode = n;
			while (tnode->down != NULL)
			{
				tnode = tnode->down;
			}
			tnode->down = temphead;
			repeat++;
			return;
		}
		else if (temp->xcor == (n->xcor) && temp->ycor == (n->ycor + 1)&&n != temp)
		{
			node *tnode = n;
			while (tnode->down != NULL)
			{
				tnode = tnode->down;
			}
			tnode->down = temphead;
			repeat++;
			return;
		}
		else if (temp->xcor == (n->xcor) && temp->ycor == (n->ycor - 1) && n != temp)
		{
			node *tnode = n;
			while (tnode->down != NULL)
			{
				tnode = tnode->down;
			}
			tnode->down = temphead;
			repeat++;
			return;
		}
		else if (temp->xcor == (n->xcor - 1) && temp->ycor == (n->ycor) && n != temp)
		{
			node *tnode = n;
			while (tnode->down != NULL)
			{
				tnode = tnode->down;
			}
			tnode->down = temphead;
			repeat++;
			return;
		}
		n = n->down;
	}
	return;
}

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

문제

문제

출처

ICPC

링크드리스트로 구현하면 시간초과가 뜨네요...

changu02 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말