https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 영역 구하기 2. 영역 중에서 바다와 맞닿은 (= 제일 끝쪽에 있는) 곳들 찾아주는 함수 작성 3. 사이드 영역에서 다른 영역까지의 최단거리 구하기 이 문제의 해결법은 크게 위 3단계로 나눌 수 있다. 1번 해결법 설명 : dist배열을 활용하여 모든 육지가 아닌, 아직 탐색하지 않은 영역인 경우에만 탐색을 진행한다. cnt 변수를 이용하여 번호를 매겨주면 된다! 2번 해결법 설명 : 바다와 맞닿..
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...
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 단순 bfs문제 + 벽을 한번 부술 수 있다는 특징이 있는 문제이다. 주요 풀이는 다음과 같다. 3차원 배열을 선언하여 거리를 저장해주는데 벽을 부수고 이동하면 [x][y][0] 에 값을 저장해주고 벽을 안부수고 이동했다면 [x][y][1]에 값을 저장해준다. 다음 이동할 좌표가 맵의 범위 안이라면, 2가지 경우로 나눈다. 1. 벽을 만났는데, 뚫을 수 ..
https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 이 문제는 bfs 기본코드에서 약간의 응용이 필요하다. 우선 갈 수 있는 방향이 1.상 2.하 3.좌 4.우 5.좌상 6.우상 7.좌하 8.우하 9.제자리 로 총 9가지다. 그리고 벽이 1초에 한 줄씩 내려온다고 하였으므로, 1초마다 벽의 위치를 움직여줘야한다. 0,0에서 부터 for문을 시작하면 벽을 내리고, 내린 벽과 기존 벽을 구분하기 어려우므로 밑에서부터 for문을 시작하여 ..
