관심이 가는 개발 보물창고

풀이 N X M 크기의 맵에서 (1,1)에서 출발해서 (N,M)까지 도달하는데 걸리는 최소의 칸 수를 구하는 문제이다. 칸 과 칸 사이는 1이라는 비용으로 생각할 수 있다. (1,1) -> (1,2) 로 가는 비용이 1이라는 뜻이다. 만약에 비용이 달랐다면 다른 방법으로 풀어야 한다. 비용이 모두 1로 같기 때문에 이 문제는 BFS 알고리즘으로 해결할 수 있다. 여기서는 (0,0) -> (N-1, M-1)로 구현했다. #include #include #include using namespace std; int n, m; int board[101][101]; bool vis[101][101]; int bfs() { int dx[] = { 0,0,-1,1 }; int dy[] = { 1,-1,0,0 }; q..

풀이 컴퓨터를 어떻게 코드 상으로 연결할지 생각하자. 이 문제에서는 주어진 간선만 표현하면 되므로 인접 리스트가 편하다. 이때 주의할 점은 양방향 간선으로 그래프를 표현해야 한다. 바이러스의 전파는 무조건 컴퓨터 1번으로부터 시작하므로 1번부터 인접한 컴퓨터를 카운트하면서 진행하면 된다. #include #include #include using namespace std; int v, e; vector computer[101]; bool vis[101]; int bfs() { int cnt = 0; queue q; q.push(1); vis[1] = true; while (!q.empty()) { int now = q.front(); q.pop(); for (int i = 0; i < computer[n..

풀이 약간의 트릭만 잘 찾아내면 쉽게 문제를 해결할 수 있다. 울타리의 최소 개수를 구하는 문제가 아니라, 울타리를 설치해서 양을 늑대로부터 보호에 성공한다면 양은 사는 것이고 아니라면 양은 늑대에게 잡아먹히게 된다. 양이 늑대로부터 살려고 한다면? 가장 간단한 방법은 양의 상, 하, 좌, 우 방향으로 울타리를 설치하면 된다. 그러고 나서 늑대가 맵을 탐색 하면서 양을 찾아내지 못한다면 양은 사는 것이고, 아니라면 잡아먹힌다. 1. 양의 상,하,좌,우 방향으로 울타리를 설치한다. (이때 빈칸인 경우에만 울타리를 설치하자.) 2. 늑대가 양을 찾는다. #include #include using namespace std; int r, c; char board[501][501]; bool vis[501][50..

풀이 핵심은 촌수 관계를 어떻게 코드로 풀어낼 것인지다. 이 문제는 N의 범위가 100밖에 되지 않기 때문에 인접 행렬 or 인접 리스트 중 하나를 선택해서 구현하면 된다. 인접 리스트로 구현한다고 할 때, 부모 자식 간의 관계를 나타내는 번호가 a, b로 주어지게 된다면, 서로 양방향으로 넣어줘야 한다는 것만 주의하면 쉽게 해결할 수 있다. #include #include #include using namespace std; // 어떻게 촌수를 표현할 지? vector v[101]; bool vis[101]; int n, m, x, y; int bfs() { queue q; q.push({ x,0 }); vis[x] = true; while (!q.empty()) { int now = q.front()..

풀이 기존 BFS로 탐색하면서 양을 발견하면 양의 수를 올려주고, 늑대를 발견하면 늑대의 수를 올려준다. 탐색이 끝나면 양의 수와 늑대의 수를 비교해서 양이 더 많다면 양이 살아남고, 아니라면 늑대가 살아남는다. 즉, 한 공간 안에서 늑대의 수와 양의 수를 비교해서 살아남는 것만 잘 구현하면 끝나는 문제. #include #include using namespace std; // 공간안에서 양이 늑대보다 많으면 양이 이기고, 아니면 늑대가 이긴다. // 문제에서 원하는 답은 남은 양과 늑대이다. int r, c; char field[251][251]; bool vis[251][251]; int sheep, wolf; int dx[] = { 0,0,-1,1 }; int dy[] = { 1,-1,0,0 };..

풀이 기초적인 BFS 알고리즘을 잘한다고 알았던 내가, 이 문제를 보고 한 동안 머리가 아펐다. 기존 BFS 알고리즘 문제들은 대부분 2차원 배열 안에서 해결할 수 있었지만, 이 문제에서는 그 프레임을 벗어나야 해결할 수 있는 문제였다. 원숭이는 기본적으로 상,하,좌,우로 이동할 수 있지만, 이 원숭이는 특별해서 K번의 말의 능력을 사용해서 마치 나이트처럼 움직일 수 있다. 즉, 기존 원숭이처럼 움직이되 어떠한 경우에서는 말의 능력을 이용하면 더 빨리 도착할 수 있다는 것이다. 핵심은 바로 방문 배열을 3차원 배열로 만드는 것이다. vis[x][y][k] : (x,y)를 k번의 능력을 사용해서 도달했는지 여부를 체크하는 방문 배열이다. 무슨 말이냐면, (4,5)를 온 경우를 생각해보자. (4,5)라는 지..