https://www.acmicpc.net/problem/2178
문제
N×M크기의 배열로 표현되는 미로가 있다.
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제 입력 1
4 6
101111
101010
101011
111011
예제 출력 1
15
정답
using System;
using System.Text;
class Program
{
//입력 값
static int n;
static int m;
// 보드와 방문 여부
static int[,] board;
static bool[,] isVisited;
// 상, 하, 좌, 우
static int[] X = { -1, 1, 0, 0 };
static int[] Y = {0, 0, -1, 1 };
static void Main(string[] args)
{
string[] input = Console.ReadLine().Split(' ');
n = int.Parse(input[0]);
m = int.Parse(input[1]);
board = new int[n, m];
isVisited = new bool[n, m];
for (int i = 0; i < n; i++)
{
string inputs = Console.ReadLine();
for (int j = 0;j < m; j++)
{
// '0'을 빼서 int값으로 변환시킴
board[i, j] = inputs[j] - '0';
}
}
int result = BFS(0,0);
Console.WriteLine(result);
}
private static int BFS(int startX, int startY)
{
// 상, 하, 좌, 우
// 위로 이동시 + X[0] + Y[0]
// 아래 이동시 + X[1] + Y[1]
// 좌측 이동시 +X[2] + Y[2]
// 우측 이동 시 + X[3] + Y[3]
Queue<(int, int, int)> queue = new Queue<(int, int, int)>();
queue.Enqueue((startX, startY, 1));
isVisited[startX, startY] = true;
while(queue.Count > 0)
{
var (x, y, distance) = queue.Dequeue();
// 도착시에 그 값을 반환함
if (x == n - 1 && y == m - 1)
return distance;
for(int i = 0; i < X.Length; i++)
{
int moveX = x + X[i];
int moveY = y + Y[i];
if(moveX >= 0 && moveY >= 0 && moveX < n && moveY < m)
{
// 방문했을 경우
if (isVisited[moveX, moveY])
continue;
// 1이 아니면 갈 수 없기 때문에
if (board[moveX, moveY] != 1)
continue;
isVisited[moveX, moveY] = true;
queue.Enqueue((moveX, moveY, distance + 1));
}
}
}
return -1;
}
}
문제 풀이
BFS로 해결한 문제이다. 미로 탐색이면 0,0 지점에서 상하좌우를 살피고 1이면 가고 0이면 가지 않는 식을 짜줘야 한다.
// 상, 하, 좌, 우
// 위로 이동시 + X[0] + Y[0]
// 아래 이동시 + X[1] + Y[1]
// 좌측 이동시 +X[2] + Y[2]
// 우측 이동 시 + X[3] + Y[3]
int[] X = { -1, 1, 0, 0 };
int[] Y = {0, 0, -1, 1 };
임의의 이동값 x와 y를 정해서 처음 0,0 에서 해당 배열만큼 상 하 좌 우를 반복문으로 돌려가면서 방문 여부와 0인지 1인지 체크, 그리고 이동할 수 있다면 이동하는 식으로 전제를 깔고 간다.
그렇다면 선언할 것은 board 2차원 배열, 방문여부 2차원 배열, 상하좌우를 표시할 x와 y의 배열이다.
//입력 값
static int n;
static int m;
// 보드와 방문 여부
static int[,] board;
static bool[,] isVisited;
// 상, 하, 좌, 우
static int[] X = { -1, 1, 0, 0 };
static int[] Y = {0, 0, -1, 1 };
Main
Main에서는 입력된 값으로 board판을 만들고, BFS를 0,0부터 호출하는 값을 만들어주도록 한다.
static void Main(string[] args)
{
string[] input = Console.ReadLine().Split(' ');
n = int.Parse(input[0]);
m = int.Parse(input[1]);
board = new int[n, m];
isVisited = new bool[n, m];
for (int i = 0; i < n; i++)
{
string inputs = Console.ReadLine();
for (int j = 0;j < m; j++)
{
// '0'을 빼서 int값으로 변환시킴
board[i, j] = inputs[j] - '0';
}
}
int result = BFS(0,0);
Console.WriteLine(result);
}
여기서 '0'을 빼 주는 이유는 기존 string으로 보드를 줄로 까는데, 이는 아스키 코드를 통해 '1' -'0'은 정수 1이 되고, '0'-'0' 은 0이 된다. 그렇게 보드판을 다 int값으로 변환해줄 수 있다.
그리고 BFS를 0,0부터 시작하면 된다.
BFS
너비우선탐색 BFS는 미로의 최단 경로를 찾는 데 유용한 알고리즘이다. 기존의 BFS식을 그대로 하면 되는데, Queue에 넣어야할 변수가 x값, y값, 그리고 계속 증가시켜 최단 거리를 나타낼 거리값 3개를 넣어야 하는데 이는 튜플(Tuple)로 가능하다.
튜플(Tuple)
튜플은 C#에서 여러 값의 데이터 구조를 하나로 묶을 수 있는 기능이다. 이를 이용하면 손쉽게 Queue에 변수 세개를 넣을 수 있다.
기존에는 클래스를 하나 생성하여 메서드에 x,y,distance 생성자를 생성 후, Queue에 해당 클래스를 받는 방식이지만, 튜플을 사용하면 더 간편하게 할 수 있다.
※ 튜플을 사용하지 않았을 때
// 튜플을 사용하지 않을 경우
Class Node
{
public int X {get; set;}
public int Y {get; set;}
public int Distance {get; set;}
public Node(int x, int y, int distance)
{
X = x;
Y = y;
Distance = distance
}
}
static int BFS(int startX, int startY)
{
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(new Node(startX, startY, 1));
}
※ 튜플을 사용했을 때
static int BFS(int startX, int startY)
{
Queue<(int, int, int)> queue = new Queue<(int, int, int)>();
queue.Enqueue((startX, startY, 1));
}
() 괄호로 필요한 데이터들을 묶어서 위와 같이 관리할 수 있다.
튜플과 함께 딸려올 수 있는 것이 패턴매칭이다. 이는 queue를 튜플로 위와 같이 데이터를 담아줬다면, 패턴 매칭을 통해 값을 꺼내와서 사용할 수 있다.
패턴 매칭
패턴 매칭은 데이터 구조 형태를 검사하고, 해당 구조에서 값을 추출하는 기능이다.
(int a, int b) = (1, 2);
Console.WriteLine(a);
Console.WriteLine(b);
위와 같은 코드이면 a에는 1, b에는 2가 할당되는 걸 볼 수 있다.
그렇다면 큐에서 값을 꺼내 할당해야 하기 때문에 패턴 매칭을 통해 아래와 같이 할 수 있다. 튜플과 마찬가지로 클래스로 사용했을 경우와 패턴매칭으로 사용했을 경우를 비교하여 보자.
※ 패턴매칭을 사용하지 않았을 때
while (queue.Count > 0)
{
Node node = queue.Dequeue();
int x = node.X;
int y = node.Y;
int distance = node.Distance;
}
※ 패턴매칭을 사용했을 때
while(queue.Count > 0)
{
var (x, y, distance) = queue.Dequeue();
}
Dequeue를 통해 빠진 데이터들을 각각 패턴매칭을 통해 지정한 변수에 데이터를 담아주게 된다. 이렇게 하면 가독성이 좋아지는 걸 볼 수 있다.
탐색
이제 Queue값을 설정했으면, 탐색을 통해 최단 경로를 알아보도록 하자. 조건이 필요한건 다음과 같다.
1. 현재 위치한 좌표 x값과 y좌표, 그리고 상하좌우를 선언해둔 배열 int X[]와 int Y[],를 더하게 되면 이동하는 값이 되는데 이를 moveX 와 moveY라고 각각 정한다면, 해당 값이 0과 같거나 커야 한다.
int moveX = x + X[i];
int moveY = y + Y[i];
(0,0)이 출발 선이기 때문에 이동했을 때의 좌표가 음수인 것은 말이 안되기 때문이다.
마찬가지로 moveX와 moveY가 판을 넘어가서는 안되기 때문에 입력값 n과 m보다는 작아야 한다.
2. 방문했을 경우 반복문을 탈출시켜 준다.
3. 판에 0이라고 표시되어 있다면 마찬가지로 반복문을 탈출시켜준다.
4. 도착했을 경우에는 도착한 거리값을 반환 한다.
5. 위 모든것에 해당하지 않으면 방문 여부를 true로 바꿔주고, 거리를 1더해주며 queue에 Enqueue하여 다음 경로를 탐색한다.
while(queue.Count > 0)
{
var (x, y, distance) = queue.Dequeue();
// 도착시에 그 값을 반환함
if (x == n - 1 && y == m - 1)
return distance;
// 상하좌우 탐색
for(int i = 0; i < X.Length; i++)
{
int moveX = x + X[i];
int moveY = y + Y[i];
// 판의 크기를 넘어가서는 안된다.
if(moveX >= 0 && moveY >= 0 && moveX < n && moveY < m)
{
// 방문했을 경우
if (isVisited[moveX, moveY])
continue;
// 1이 아니면 갈 수 없기 때문에
if (board[moveX, moveY] != 1)
continue;
isVisited[moveX, moveY] = true;
queue.Enqueue((moveX, moveY, distance + 1));
}
}
회고
Class를 통해 경로 탐색을 했었는데 튜플과 패턴매칭을 통해 코드의 가독성과 간결함을 올릴 수 있었고, 새로운 걸 배울 수 있는 기회였다.
'백준 등 알고리즘' 카테고리의 다른 글
| [C#] 백준 거스름돈 14916 (그리디 알고리즘) (0) | 2024.06.24 |
|---|---|
| [C#] 프로그래머스 Lv.2 n^2 배열 자르기 (0) | 2024.06.18 |
| [C#] 프로그래머스 Lv.2 연속 부분 수열 합의 개수 (1) | 2024.06.11 |
| [C#] 프로그래머스 Lv.2 N개의 최소공배수 (Linq) (1) | 2024.06.09 |
| [C#] 백준 2606번 바이러스 (1) | 2024.06.03 |