Jonyo Programming

[BOJ 4179(G3) 리뷰] 지훈이가 미로에 갇혀있다. 미로에 불이나서 불이 1분에 한칸씩 옮겨간다고 한다. 지훈이도 1분에 한칸씩 이동할 수 있다. 주어진 미로에서 지훈이가 과연 탈출할 수 있는지 구하고 탈출한다면 가장 빨리 탈출하는데에 몇초가 걸리는지 구해야한다. 탈출하지 못하면 IMPOSSIBLE을 출력해야한다. 입력은 다음과 같이 주어진다. 4 4 #### #JF# #. .# #. .# 새로운 유형이라 접근방법이 굉장히 어려웠다. 힌트를 보고 풀었다. 문제를 풀기 위해선 먼저 불이 옮겨가는 시간에 대해 탐색을 수행해야 한다. 그 후에 지훈이의 위치로부터 탐색을 시작하자. 지훈이가 가고자하는 위치가 이미 먼저 불이 옮긴 위치라면 그곳으로 이동할 수 없다. 벽을 만나게되면 탈출에 성공한것이므로 거..

입력 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다. 출력 첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다. [BOJ 2584(G4) 리뷰] 쉬운듯 어려웠다. 빙산의 높이가 주어진다. 빙산은 주위에..

[BOJ 2206(G4) 리뷰] 진짜 어려웠던 문제.. 첨에 머리싸매고 아무리 고민해도 풀이가 안떠올랐다. 벽이 있을때랑 없을때랑 해서 어찌저찌 해볼려했지만 도저히 풀리지 않았고 3D배열을 사용한다는 힌트를 봤을때 그제서야 조금씩 코딩을 할 수 있었다. 이 문제의 핵심은 '1.벽을 한번도 부수지 않고 목적지에 도착하는 경우' 와 '2.벽을 한번 부수고 목적지에 도착하는 경우' 로 나누어 계산해야한다. 따라서 거리를 기록하는 배열을 기존 2D배열에서 3D배열로 확장하여 진행 했다. 로직은 다음과 같다. 시작점 (1,1)에 방문표시를 하고 BFS를 시작한다. 상,하,좌,우 네가지 방향에 대해 방문을 실시한다. 만약 BFS를 진행중에 벽이 나타났다면 현재까지 벽을 부순적이 있는지 없는지 확인하고 벽을 부순적이..

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. 이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다. 어떤 지역의 ..

[BOJ 10025(G5) 리뷰] RGB색상이 주어지는데 적록색약은 빨간색과 초록색을 구분하지 못한다고 한다. 각각의 색깔이 구분되는 구역의 수를 세야한다. 정상인은 세가지 색에 대해 구분을 할 수 있지만 적록색약은 빨간색과 초록색을 한가지 색으로 구분하게 된다. 이 때 정상인이 바라보는 구역과 적록색약이 바라보는 구역의 수를 각각 출력하면된다. 한번의 연산만으로 수행할 수 있을까싶어 머리를 굴려봤지만 아이디어가 떠오르지 않았다. 그래서 그냥 BFS를 정상인의 경우와 적록색약의 경우로 나누어 탐색하여 결과값을 출력했다. 1= n) continue; if (check[nx][ny] != '0' || board[nx][ny] != color) continue; check[nx][ny] = color; Q.p..

[BOJ 7562(S2) 리뷰] 난 그림만 나오면 쫄고 시작하는데 그리 어려운 문제는 아니다. 기존에 상,하,좌,우 4방향 탐색하던것을 8개의 방향에대해 탐색을 하면된다. board배열에 길이를 저장하여 목적지의 길이가 몇인지 출력하면 된다. #include #include #include #include #include #include #include #include #include #include using namespace std; #define X first #define Y second int board[301][301]; int dx[8] = { 1,1,-1,-1,2,2,-2,-2 }; int dy[8] = { 2,-2,2,-2,1,-1,1,-1 }; int main(void) { cin.ti..

[BOJ 2667(S1) 리뷰] 전에 풀었던 영역구하기 문제와 아주 유사하다. (아니 오히려 쉽다) 영역구하기 문제는 입력값에 대해 집적 칠해야하는 번거로움이 있었지만 이 문제는 배열을 통째로 줘서 아주 편하다. 영역구하기 코드에서 보드판을 string으로 바꾼거 빼면 코드가 거의 흡사하다. #include #include #include #include #include #include #include #include #include #include using namespace std; string board[26]; bool check[26][26]; priority_queue result; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; int main(v..

[BOJ 2583(S1) 리뷰] 첨엔 문제 읽고 이해가 안되서 멍때렸다. 천천히 읽어보니 M*N의 직사각형에 K개의 직사각형이 주어지고 그 직사각형을 제외한 영역이 몇개로 나뉘며 나뉜 영역들의 넓이는 몇인지 구하는 문제이다. 입력값이 2 0 4 4 이런식으로 입력이 들어오면 (2,0)부터 (4,4)까지가 직사각형의 영역이다. 이 점이 좀 헷갈렸지만 이중for문을 통하여 직사각형 영역을 색칠했고 나머지 영역에 대해 BFS를 수행했다. 직사각형 영역을 색칠하는것까지만 하면 나머진 전형적인 BFS이므로 쉽게 해결할 수 있다. 각 영역들의 넓이를 오름차순으로 출력하라 했기에 그냥 우선순위큐를 사용했다. #include #include #include #include #include #include #includ..

[BOJ 7569 (S1) 토마토 리뷰] 토마토 2D버전을 푼 경험이 있기에 쉽게 풀었다. 기존 4방향에서 확인하던것을 '상,하,좌,우,위,아래' 6가지 경우에 대해 BFS를 수행하면된다. 한가지 생각해야 할점은 익은 토마토가 여러개 존재할 수 있으므로 시작할때 존재하는 익은 토마토 모두에 대해 BFS를 수행해야 한다. 이는 익은 토마토를 미리 Q에 push함으로써 해결할 수 있다. 1일에 1칸씩 이동할 수 있기에 BFS를 수행할때마다 현재위치+1를 해주면 가장 거리값이 큰 위치가 마지막으로 토마토가 익는 위치이다. #include #include #include #include #include #include #include #include #include #include using namespace ..

[BOJ 9466 (G4) 리뷰] 처음엔 간단해보였지만 풀다보니 생각하지 못한 경우의 수 때문에 애를 많이 먹었다. 처음엔 단순히 싸이클이 존재할때만 해당 학생들을 제외하여 코딩을 했는데 틀렸다고 나왔고 반례를 찾아보니 1->3->5->3과 같이 중간부터 싸이클이 시작될 경우를 고려하지 않았다. 다시 머리를 싸맨 후 싸이클이 도는 학생들만 제외를 시키도록 하였고 제출을 했으나 시간초과가 나왔다.... 코드 중간에 싸이클에 속하지않은 학생들을 걸러내는 작업에서 O(n^2)가 되었던것 같다. 포기할까 했지만 억지스러운 최적화 후에 정답처리가 되었다. 효율적인 코드인지는 모르겠다 .. #include #include #include #include #include #include #include #includ..