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가 가장 적합한 수단이라고 볼 수 있다. 학..

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

1. 문제: https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 2. 풀이 Stack을 응용한 대표적인 문제를 꼽으라면 단연 괄호와 관련된 문제라고 할 수 있다. 괄호의 쌍이 올바르게 되어 있는가를 판단할 때 스택의 특성을 가장 적극적으로 활용할 수 있는데, 여는 괄호는 스택에 넣고 닫는 괄호는 스택에서 pop을 해 쌍을 확인함으로써 풀이할 수 있다. 문제 해석에 앞서 잠시 올바른 괄호의 쌍인가를 확인하는 코드를 정리하고 간다. // '()' 소..

1. 문제: https://www.acmicpc.net/problem/9328 9328번: 열쇠 문제 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열 www.acmicpc.net 2. 풀이 지도 상에서 돌아다니면서 문을 만났을 때 열쇠가 있다면 열고 들어가고 없으면 열지 못하는 본 문제와 비슷한 유형의 문제를 백준에서 풀었던 기억이 있다. 그 문제가 뭐였는지 기억한다면 첨부하도록 하겠다.... 아무튼 문제의 상근이가 문서를 훔치기 위해서 빌딩 내부를 돌아다녀야 하는데 문제의 중요한 몇 가지만 인지하고 있다면 크게 어려울 것은 없다. 1) 상근이의 출발점이 정해지지 않았으..