[BOJ 5014(G5) 리뷰] 강호씨가 엘리베이터를 타고 특정층에 가려고 한다. 현재 강호씨의 위치와 강호씨가 가고자 하는 층이 주어지고 U와 D값이 주어지는데 위로 가는 버튼을 클릭하면 위로 U층을 가며 아래로 가는 버튼을 누르면 아래로 D층을 간다. 강호씨가 현재 위치에서 가고자 하는 위치까지 버튼을 총 몇번 눌러야 하는지 출력해야 한다. 전에 풀어봤던 문제와 비슷해서 쉽게 구현할 수 있었다. #include #include #include #include #include #include #include #include #include using namespace std; int elev[2000002]; int main(void) { cin.tie(0); ios::sync_with_stdio(0)..
입력 첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다. 출력 첫째 줄에 가장 짧은 다리의 길이를 출력한다. [BOJ 2146(G3) 리뷰] 지도에 여러섬이 존재한다. 각 섬에서 다른섬으로 가는 최단경로를 찾아야 한다. 나는 다음과 같이 풀었다. 1.인접한 영역이 같은 섬이므로 1차적으로 BFS를 수행해 각 섬마다 index를 부여했다. 2.(1,1)부터 (n,n)까지 모든 경우에 대해서 현재의 섬index에서 다른 섬의index까지 도달하는데 걸리는 거리의 최소값을 구했다. 모든 경우의 수에서 탐색을 진행하다보니 시간복잡도는 엄청나게 증가..
[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..
- Total
- Today
- Yesterday
- 구현
- 투포인터
- nodeJS
- ReactNative
- Computer Architecture
- 세그먼트 트리
- 컴퓨터 구조
- nest.js
- 백트래킹
- dfs
- 중앙대학교
- 알고리즘
- 그래프
- 동적계획법
- 스레드
- typeORM
- boj
- 그리디
- BFS
- 시뮬레이션
- 재귀
- java
- 컴퓨터 통신
- 자바
- nestjs
- 예외처리
- node.js
- 자바스크립트
- 백준
- 벨만포드
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |