LeetCode 62. Unique Path

Level은 Medium으로 책정되었지만 좀 더 쉬운 난이도의 문제이다.

데이터 구조 Queue를 사용하고 Dynamic Programming 개념을 차용하면 풀 수 있다.

class Solution {
public:
	int uniquePaths(int m, int n) {
		int arr[100][100] = { 0 };
		int AlreadyQueue[100][100] = { 0 };
		queue<pair<int, int>> grid;
		pair<int, int> SearchGrid;

		grid.push(make_pair(0, 0));
		arr[0][0] = 1;

		while (!grid.empty())
		{
			SearchGrid = grid.front();
			grid.pop();

			// Go Down
			if (SearchGrid.first < (m - 1)){
				arr[SearchGrid.first + 1][SearchGrid.second] += arr[SearchGrid.first][SearchGrid.second];

				if (AlreadyQueue[SearchGrid.first + 1][SearchGrid.second] == 0){
					grid.push(make_pair(SearchGrid.first + 1, SearchGrid.second));
					AlreadyQueue[SearchGrid.first + 1][SearchGrid.second] = 1;
				}
				else{
					// Do Nothing
				}
			}
			else{
				// Do Nothing
			}

			// Go Right
			if (SearchGrid.second < (n - 1)){
				arr[SearchGrid.first][SearchGrid.second + 1] += arr[SearchGrid.first][SearchGrid.second];

				if (AlreadyQueue[SearchGrid.first][SearchGrid.second + 1] == 0){
					grid.push(make_pair(SearchGrid.first, SearchGrid.second + 1));
					AlreadyQueue[SearchGrid.first][SearchGrid.second + 1] = 1;
				}
				else{
					// Do Nothing
				}

			}
			else{
				// Do Nothing
			}
		}

		return arr[m - 1][n - 1];
	}
};