1. 문제 25513번: 빠른 오름차순 숫자 탐색 5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자에는 -1, 0, 1, 2, 3, 4, 5, 6중 하나의 수가 적혀 있다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c www.acmicpc.net 2. 풀이 전형적인 BFS를 통한 경로탐색 문제이며, 방문해야 하는 노드가 순차적으로 정해져 있는 형태의 문제다. 우선 보드가 5 x 5 로 작은 형태이므로 구현 자체에도 큰 어려움이 없을 것으로 생각된다. 다만, 이미 방문한 노드를 어떻게 다시 방문하지 않을 것인가를 판단하는 것이 중요한데, 대개 이러한 유형의 경우 3차원 배열로 방문배열을 선언하여 현재 탐색중인 idx 에서는 중복된 칸을 ..

1. 문제 12887번: 경로 게임 첫째 줄에 바꿀 수 있는 하얀색 칸의 개수의 최댓값을 출력한다. www.acmicpc.net 2. 풀이 문제가 다속 복잡해보이기 위해 노력했으나 사실 핵심을 간파하기는 쉬운 유형이다. 격자판의 하얀색 칸을 검정색 칸으로 바꾼 경우에도 왼쪽-오른쪽 경로가 존재할 수도 있다. 이때, 왼쪽-오른쪽 경로가 존재하면서 바꿀 수 있는 하얀색 칸의 최댓값을 구하는 프로그램을 작성하시오. 왼쪽-오른쪽 경로가 항상 존재하는 게임판만 입력으로 주어진다. 이를 다시 정리하자면, 좌측 끝에서 우측 끝으로 가는 경로에서 방문하지 않은 칸의 개수를 최대로 만들라는 말이며, 이는 곧 최소경로를 찾으라는 말과 동일하다. 그렇다면 우리는 아래의 과정을 통해서 본 문제를 풀 수 있게 된다. 입력과 동..

1. 문제 20304번: 비밀번호 제작 서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부 www.acmicpc.net 2. 풀이 결과적으로 어떤 답을 만들어내야 하는가가 다소 헷갈릴 수 있는 문제의 유형이라 생각한다. 그 중 먼저 문제의 핵심인 안전거리와 안전도를 판단하는 방법을 알아본다. 2.1 안전거리와 안전도 3, 4 두 가지의 비밀번호가 입력된 적 있을 때, 2라는 비밀번호를 설정했을 때의 안전거리를 알아보자. 먼저 2, 3, 4를 이진수로 변환하면 아래와 같다. 3: 0011 4: 0100 2: 0010 (2,3)의 경우 서로다른 비트가 한 개이기 때문에 안전거리는..

1. 문제 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 2. 풀이 본 문제는 다소 복잡해 보이지만, BFS를 이용한 구역나누기 문제이며 잡다구리한 비즈니스 로직(빙산이 녹는 것)은 시뮬레이션 문제라고 볼 수 있다. 문제에 주어진 조건들을 순수하게 따라서 비즈니스 로직을 구현하고, 빙산이 녹아서 두 구역으로 나뉘어졌는지만 그래프 탐색을 통해 해결한다면 어렵지 않은 문제! 중요한 조건인 빙산이 부리되지 않고 한 번에 모두 녹는 경우 0을 반환하는 조건만 잘 체크해준다면 큰 어려움 없이 풀 수 있다. 3...

1. 문제 16959번: 체스판 여행 1 크기가 N×N인 체스판이 있고, 체스판의 각 칸에는 1부터 N2까지의 정수가 한 번씩 적혀있다. 지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다. 지학이가 가지고 있는 말은 나이트, www.acmicpc.net 2. 풀이 BFS를 응용해볼 수 있는 좋은 유형의 문제로, 문제의 조건에 따라 말의 방문 처리를 어떻게 꼼꼼하게 할 것 인가가 문제의 키 포인트이다. 먼저 지학이가 수행할 수 있는 동작과 조건을 살펴보자. 1) 동작 말을 다른 유형의 말로 변경한다(나이트, 룩, 비숍) 말을 이동시킨다 2) 조건 같은 칸을 여러 번 방문해도 된다. 1부터 N² 까지 각 칸을 순차적으로 방문해야 한다. 번호에 따라 순차적으로 방문해야 하므로, 체스판을 입력 받음과..

1. 문제 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 2. 풀이 우선 (1, 1) 에서 (N, N)으로 가는 모든 경로를 탐색해야 하는 BFS 문제임은 맞지만, (최대 - 최소) 값이 최소가 되게 만들기 위해서 경로를 탐색하기 위해서는 특정한 기준이 필요하다. 여기서 기준이란 모든 경우를 만들어서 값을 만들어 볼 수는 없으니, 기준값을 만들어 해당 값으로 배열에서 (1, 1)부터 (N, N)까지의 경로가 있는지 확인하는 것이다. 그렇다면 이 기준을 어떻게 만들어 줄 것 인가에 초점..

1. 문제 26999번: Satellite Photographs Farmer John purchased satellite photos of W x H pixels of his farm (1 ≤ W ≤ 80, 1 ≤ H ≤ 1000) and wishes to determine the largest 'contiguous' (connected) pasture. Pastures are contiguous when any pair of pixels in a pasture can be connected by tra www.acmicpc.net 2. 풀이 해당 문제는 좌표계에서 BFS를 이용하여 Grouping 하는 기초를 다질 수 있는 문제다. 문제를 요약하자면 아스트리크(*) 로 연결된 가장 넓은 영역을 구하라는..

1. 문제 25416번: 빠른 숫자 탐색 5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자에는 -1, 0, 1중 하나의 숫자가 적혀 있다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호 www.acmicpc.net 2. 풀이 전형적인 미로 탐색 문제이다. BFS의 개념을 이해하고 있다면 Standard와 같은 문제이므로 큰 어려움 없이 풀이가 가능하다. 네 방위(동, 서, 남, 북)로 움직일 수 있는 학생이 움직일 수 없는 조건에 대해서만 적절하게 체크해주면 풀이가 가능하다. 까다로운 조건 없이 좌표계에서 이동만 하는 것이며, `1`이 적힌 어딘가에 있는 지점으로 도달해야하므로 BFS가 가장 적합한 수단이라고 볼 수 있다. 학..

BFS(너비 우선 탐색) 알고리즘에 대해 알아보기 전에 필수적으로 알아봐야 할 자료구조는 바로 그래프(Graph)다. 그래프는 실질적으로 프로그래밍 언어 라이브러리 상에서 제공하기 보다는 추상적인 자료구조로써 개념을 차용하여 알고리즘에 응용하여 푸는 경우가 많으므로, 자료구조 카테고리가 아닌 알고리즘 카테고리에서 함께 다루고자 한다. 그래프 그래프의 정의 및 개념 그래프(G)는 정점 집합(V)과 간선 집합(E)으로 구성된 자료구조로, 대상과 대상 간의 관계를 나타내는 자료구조다. 그래프는 다들 너무나도 익숙하게 들어봤을 '쾨니히스베르크(Königsberg) 다리'를 보고 수학자 오일러가 '한붓그리기' 문제를 해결하기 위해 고안한 것으로 알려져 있기도 하다. 이 고안법에서 중요한 것은, 각 육지를 잇는 다..

1. 문제: https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, www.acmicpc.net 2. 풀이 문제의 핵심 조건은 아래와 같다. 1) 상하좌우 뿐만 아니라 대각선으로도 움직일 수 있다. 2) 방문하는 장소들 중 고도의 최고점과 최저점의 차이를 '피로도'라고 하며 이를 최소화 해야한다. 대각선을 추가하는 것이야 방향을 설정해주는 dy, dx 배열만 추가로 설정해주면 되는데 피로도를 최소화하기 위해서는 어떤 방법을 써야할 것 인가? 지도에서 주어진 모..