글 읽기 - 답은 맞지만 시간초과 리스트문제임다ㅜ 제가 너무 어렵게하나요

kiyoon123 4년 전 0

list 두개 선언해서

row 나타내는 리스트 col 나타내는 리스트 두개로 해서

자료구조를 해봤는데

점프할 곳 탐색할때 꽃들만 있는 좌표를 list 에 넣었긴 하지만 1,1 부터 점프할 좌표까지

결국 iter로 탐색을 시켜서 시간 초과가 나오는 건가요??? ㅠㅜ

#include <iostream>
#include <list>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;


class RowNode {
	friend class Array;
private:
	int row;
	list<int> colNode;
public:
	RowNode(int r) :row(r) {

	}
	bool operator<(const RowNode& other) {
		if (this->row < other.row)
			return true;
		else
			return false;
	}

};

class Array {
private:
	int rowCount;
	int colCount;
	int rowPos, colPos;
	list<RowNode> rowNode;
public:
	Array() :rowCount(0), colCount(0), colPos(0), rowPos(0) {

	}
	void InitFrog(int r, int c) {
		rowPos = r;
		colPos = c;
	}
	void Create(int r, int c) {
		rowNode.push_back(r);
		list<RowNode>::iterator it = --rowNode.end();
		it->colNode.push_back(c);

		if (r > rowCount)
			rowCount = r;
		if (c > colCount)
			colCount = c;
	}
	void Sort() {
		rowNode.sort();
		for (auto it = rowNode.begin(); it != rowNode.end(); it++) {
			it->colNode.sort();
		}
	}
	void Delete(int rowDel, int colDel) {
		for (auto rowit = rowNode.begin(); rowit != rowNode.end(); rowit++) {
			if (rowit->row == rowDel) {
				for (auto colit = rowit->colNode.begin(); colit != rowit->colNode.end(); colit++) {
					if (*colit == colDel) {
						rowit->colNode.erase(colit);
						break;
					}
				}
				break;
			}
		}

	}
	void JumpA() {

		int tmprow = rowPos+1, tmpcol = colPos+1;
		while (tmprow <= rowCount && tmpcol<=colCount) {

			for (auto rowit = rowNode.begin(); rowit != rowNode.end(); rowit++) {
				if (rowit->row == tmprow) {
					for (auto colit = rowit->colNode.begin(); colit != rowit->colNode.end(); colit++) {
						if (*colit == tmpcol) {
							Delete(rowPos, colPos);
							rowPos = tmprow;
							colPos = tmpcol;
							break;
						}

					}
					break;
				}
			}
			tmprow++;
			tmpcol++;
		}
	}
	void JumpB() {

		int tmprow = rowPos+1, tmpcol = colPos-1;
		while (tmprow <=rowCount && tmpcol>=1) {

			for (auto rowit = rowNode.begin(); rowit != rowNode.end(); rowit++) {
				if (rowit->row == tmprow) {
					for (auto colit = rowit->colNode.begin(); colit != rowit->colNode.end(); colit++) {
						if (*colit == tmpcol) {
							Delete(rowPos, colPos);
							rowPos = tmprow;
							colPos = tmpcol;
							break;
						}

					}
					break;
				}
			}
			tmprow++;
			tmpcol--;
		}
	}
	void JumpC() {

		int tmprow = rowPos-1, tmpcol = colPos+1;
		while (tmprow>=1 && tmpcol<=colCount) {

			for (auto rowit = rowNode.begin(); rowit != rowNode.end(); rowit++) {
				if (rowit->row == tmprow) {
					for (auto colit = rowit->colNode.begin(); colit != rowit->colNode.end(); colit++) {
						if (*colit == tmpcol) {
							Delete(rowPos, colPos);
							rowPos = tmprow;
							colPos = tmpcol;
							break;
						}

					}
					break;
				}
			}
			tmprow--;
			tmpcol++;
		}
	}
	void JumpD() {

		int tmprow = rowPos-1, tmpcol = colPos-1;
		while (tmprow >=1 && tmpcol >= 1) {

			for (auto rowit = rowNode.begin(); rowit != rowNode.end(); rowit++) {
				if (rowit->row == tmprow) {
					for (auto colit = rowit->colNode.begin(); colit != rowit->colNode.end(); colit++) {
						if (*colit == tmpcol) {
							Delete(rowPos, colPos);
							rowPos = tmprow;
							colPos = tmpcol;
							break;
						}

					}
					break;
				}
			}
			tmprow--;
			tmpcol--;
		}
	}
	void Result() {
		cout << rowPos << " " << colPos << endl;
	}
	
};

int main() {
	int plantNum, moveNum;
	Array Frog;
	cin >> plantNum >> moveNum;
	char* move = new char[moveNum];
	for (int i = 0; i < moveNum; i++)
		cin >> move[i];

	for (int i = 0; i < plantNum; i++) {
		int r, c;
		cin >> r >> c;
		Frog.Create(r, c);
		if (i == 0)
			Frog.InitFrog(r, c);
	}
	Frog.Sort();
	for (int i = 0; i < moveNum; i++) {
		switch (move[i]) {
		case 'A':
			Frog.JumpA();
			break;
		case 'B':
			Frog.JumpB();
			break;
		case 'C':
			Frog.JumpC();
			break;
		case 'D':
			Frog.JumpD();
			break;
		default:
			break;
		}
	}
	Frog.Result();
}

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

문제

문제

출처

ICPC

답은 맞지만 시간초과 리스트문제임다ㅜ 제가 너무 어렵게하나요

kiyoon123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말