https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 오랜만에 푼 bfs 문제이다. 보물의 위치가 정해져있지 않기 때문에, 브루트포스를 이용하여 보물의 위치를 정해주는 것이 필요하다. 모든 육지(L)에 대해 bfs 탐색을 진행해주는데, 첫번째 L에 대해 bfs 탐색을 하고 얻게 된 가장 긴 길이가 5라고 할 때, bfs함수는 5를 반환하고 ans 변수에 저장한다. 지도를 초기화해준뒤, 2번째로 만나는 L에 대해 bfs 탐색을 하고 얻게 된 가장 긴 길이..
https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 영역 구하기 2. 영역 중에서 바다와 맞닿은 (= 제일 끝쪽에 있는) 곳들 찾아주는 함수 작성 3. 사이드 영역에서 다른 영역까지의 최단거리 구하기 이 문제의 해결법은 크게 위 3단계로 나눌 수 있다. 1번 해결법 설명 : dist배열을 활용하여 모든 육지가 아닌, 아직 탐색하지 않은 영역인 경우에만 탐색을 진행한다. cnt 변수를 이용하여 번호를 매겨주면 된다! 2번 해결법 설명 : 바다와 맞닿..
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 이 문제.. 분명 맞게 푼 것 같은데 자꾸 시간초과가 나시는 분들이 있을 것이다. 아래 코드를 보자 if (nx = n || ny = m) continue; // 이미 방문한 경우 if (visited[nx][ny][wall]) continue; if (board[nx][ny] == 0) { q.push({nx,ny,ans..
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 이 문제는 단순 bfs + 약간의 구현이라고 생각한다. 16509번 장군 문제를 풀고 오시면 뭔가 비슷한데..? 라고 느끼실 수 있다. 그러나! 이 문제의 요점은 바로 원숭이가 말(馬)처럼 K번 움직일 수 있다는 것이다. 때문에 주의할 점이 2가지 존재한다. 1. 한 점에서 탐색을 할 때 말처럼 움직일 수 있으면 말처럼 움직이고, 상하좌우 탐색도 같이 해줘야한다는 것! 2. 아래 ..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 구현 + bfs 문제라서 조금 까다로웠다. 보통 구현, 시뮬레이션 이쪽 문제들은 꼼꼼히 읽고 자잘하게 챙겨줘야하는 것들이 많으니 유의하시길 바란다! 우선, 원소 하나하나에 대해 bfs를 해준다. bfs에 들어가기 전에 연합 정보를 저장할 벡터를 이용해 벡터에 탐색을 '시작하는' 곳의 좌표를 넣어주고, 연합의 인구 수를 계산할 변수인 sum에 현재 나라의 인구 수를 저장해준다. bfs..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 이 문제는 bfs에 구현을 섞은 문제이다. 총 3가지의 주요 로직으로 이루어져 있다. 1. 가장자리 입력부터 차근차근히 보자면, 입력을 받을 때 0행, 마지막 행, 첫 열, 마지막 열은 가장자리로써 상근이가 자유로이 접근할 수 있기 때문에 모두 큐에 넣어주자. 그러나! 가장자리에는 벽이 올 수도 있고, 문 또는 키, 그리고 빈칸 모두가 올 수 있다. 그러므로 입력을 받을 때 이들을 걸러주자. case1...
