문제 설명
- 가로 N, 세로 M이 주어진다.
- 시작점은 좌측 상단
- 도착점은 우측 하단
- 이동은 우측과 하단만 가능
- 시작점이 도착점일 수 있음
문제 풀이1
이 문제는 BFS, DFS, DP로 풀 수 있는 문제로 분류되어 있다.
우선 익숙한 DFS로 풀이를 해보았다.
아래는 코드다.
더보기
using System;
using System.Collections.Generic;
namespace StudyCS
{
class Program
{
public struct Location
{
public Location()
{
x = 0;
y = 0;
}
public int x;
public int y;
}
public struct Map
{
public int[,] mapData;
public int horizontalMapMax;
public int verticalMapMax;
}
public static void Main(string[] args)
{
//가로N
//세로M
//이동은 우측과 하단만
//시작 위치는 북서
//도착 위치는 남동
//시작 위치가 도착지일 수 있음
int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
Map map = new Map();
map.horizontalMapMax = input[0];
map.verticalMapMax = input[1];
map.mapData = new int[map.verticalMapMax, map.horizontalMapMax];
//입력받기
//1은 갈 수 있음
//0은 갈 수 없음
for(int i = 0; i < map.verticalMapMax; i++)
{
int[] oneLine = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
for (int j = 0; j < map.horizontalMapMax; j++)
{
map.mapData[i, j] = oneLine[j];
}
}
Location location = new Location();
bool success = Search(location, map);
if (success)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
public static bool Search(Location inLocation, Map inMap)
{
bool success = false;
//Console.WriteLine($"Now Position : ({inLocation.x}, {inLocation.y})");
//도착지일 경우
if(inLocation.x == inMap.horizontalMapMax-1 && inLocation.y == inMap.verticalMapMax-1)
{
success = true;
return success;
}
if(inLocation.x + 1 < inMap.horizontalMapMax)
{
if (inMap.mapData[inLocation.y, inLocation.x + 1] == 1)
{
inLocation.x += 1;
success = success | Search(inLocation, inMap);
inLocation.x -= 1;
}
if(success)
{
return success;
}
}
if (inLocation.y + 1 < inMap.verticalMapMax)
{
if (inMap.mapData[inLocation.y + 1, inLocation.x] == 1)
{
inLocation.y += 1;
success = success | Search(inLocation, inMap);
inLocation.y -= 1;
}
if (success)
{
return success;
}
}
return success;
}
}
}이 코드는 dfs(깊이 우선 탐색) 알고리즘으로 풀이해보려고 하였다.
DFS란?
한 정점에서 끝까지 탐색하는 방식의 알고리즘이다.
코드 설명
재귀식으로 시작점(0,0)에서 맵의 크기보다 작은 경우 탐색해서 갈 수 있는 경우 true를 반환하고 모든 경우의 수를 탐색하여 비트 연산자 |를 통해 합연산으로 결과를 도출하는 코드이다.
코드 실패
그리고 당연하게 시간 초과가 떠버렸다.
모든 경우의 수를 탐색하는 알고리즘으로 구현해서 그런가보다.
백트래킹으로 구현하면 시간초과가 안뜰지는 모르겠으나 이번엔 BFS(너비 우선 탐색) 알고리즘으로 구현해보고자 하였다.
BFS란?
한 정점에서 주변 정점을 탐색하고 정점에 방문했는지 기록하는 알고리즘이다.
가까운 순서대로 갈 수 있는 지점을 추가하고 꺼내 사용하기 때문에 Queue 자료구조와 반복문을 보통 사용한다.
문제 풀이2
아래는 코드이다.
더보기
using System;
using System.Collections.Generic;
namespace StudyCS
{
class Program
{
public struct Location
{
public Location()
{
x = 0;
y = 0;
}
public int x;
public int y;
}
public struct Map
{
public int[,] mapData;
public int horizontalMapMax;
public int verticalMapMax;
}
public static void Main(string[] args)
{
//가로N
//세로M
//이동은 우측과 하단만
//시작 위치는 북서
//도착 위치는 남동
//시작 위치가 도착지일 수 있음
int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
Map map = new Map();
map.horizontalMapMax = input[0];
map.verticalMapMax = input[1];
map.mapData = new int[map.verticalMapMax, map.horizontalMapMax];
//입력받기
//1은 갈 수 있음
//0은 갈 수 없음
for(int i = 0; i < map.verticalMapMax; i++)
{
int[] oneLine = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
for (int j = 0; j < map.horizontalMapMax; j++)
{
map.mapData[i, j] = oneLine[j];
}
}
bool success = Search(map);
if (success)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
public static bool Search(Map inMap)
{
Queue<Location> queue = new Queue<Location>();
bool[,] visited = new bool[inMap.verticalMapMax, inMap.horizontalMapMax];
//시작 위치 설정
queue.Enqueue(new Location());
visited[0, 0] = true;
while(queue.Count > 0)
{
Location location = queue.Dequeue();
if (location.x == inMap.horizontalMapMax - 1 && location.y == inMap.verticalMapMax - 1)
{
return true;
}
Location nextLocation = new Location();
//오른쪽으로 이동
nextLocation.x = location.x + 1;
nextLocation.y = location.y;
if(nextLocation.x < inMap.horizontalMapMax && !visited[nextLocation.y, nextLocation.x] && inMap.mapData[nextLocation.y,nextLocation.x] == 1)
{
queue.Enqueue(nextLocation);
visited[nextLocation.y, nextLocation.x] = true;
}
//아래쪽으로 이동
nextLocation.x = location.x;
nextLocation.y = location.y + 1;
if (nextLocation.y < inMap.verticalMapMax && !visited[nextLocation.y, nextLocation.x] && inMap.mapData[nextLocation.y, nextLocation.x] == 1)
{
queue.Enqueue(nextLocation);
visited[nextLocation.y, nextLocation.x] = true;
}
}
return false;
}
}
}코드 설명
위에서 bfs알고리즘에 대해 설명한 것과 같이 Queue와 반복문을 사용해 구현한다.
또한 특이점으로는 방문했던 정점에 대해서 기록한다.
이를 통해서 Queue에서 방문했던 정점을 꺼낸 경우에도 체크해서 넘어갈 수 있기 때문에 효율적이다.