BFS

[1697] 숨바꼭질(C++)

문제 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 해결 방법 살짝 까다로웠던 문제. 분명 트리로 푸는건 아닌 것 같은데 자꾸 트리만 생각나고 bfs로 어떻게 풀어야할지 감이 안잡혀서 결국 구글링을 했다. 알고리즘은 간단하다. 1. 수빈이의 위치(n)..

[10026] 적록색약(C++)

문제 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 www.acmicpc.net 해결 방법 한 번에 맞은 문제가 진짜 오랜만인 것 같다 ㅋㅋ 좀 더 빨리 풀 수 있었는데 visited[i][j]가 초기화가 제대로 되지 않았던 탓에 시간을 좀 끌었다. 분명히 구글링한 결과로는 이..

[2583] 영역 구하기(C++)

문제 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. www.acmicpc.net 해결 방법 저번주에 도전하다가 결국 실패해서 과제로 제출하지 못한 문제이다. 연휴라 시간도 많고 이걸 해결하지 못하면 다른 bfs문제도 풀 수 없을 것 같아서 다시 도전하기로 했다. 내가 생각하는 좌표의 시작점..

[2178] 미로 탐색(C++)

문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해결 방법 DFS보다 BFS가 개인적으로 코드가 더 복잡하게 느껴져서 그런지 DFS로 풀 수 있는 문제는 무조건 DFS로 풀었더니 BFS로 푼 문제가 없어서 참고할 코드가 없었다... BFS 개념도 다시 찾아보고 결국 코드도 구글링 하긴 했다. 앞으로는 무조건 내 힘으로만 풀 수 있길.. 이 코드에서 가장 중요한 부분은 25, 54번째 줄인 것 같다. 미로를 int형으로 받는데 공백이 없이 들어오기 때문에 char형으로 선언하고 %s나 %c로 받는 방법도 있겠지만 %1d로 받음으로써 배열..

[1012] 유기농 배추

문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 해결 방법 [2667] 단지번호붙이기와 정말정말 유사한 문제 같아서, 유사한 문제여서 야심차게 도전했는데 예제와 질문 게시판의 모든 testcase들을 돌려보고 올바르게 실행이 됨에도 불구하고 ..

[2667] 단지번호붙이기(C)

문제 [2667] 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수..

[2606] 바이러스

문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. www.acmicpc.net 🔎 해결 방법 dfs를 실행할때마다 count(바이러스에 감염된 컴퓨터의 수) 1 증가 연결 요소의 개수(cc)가 2이상이라는 것은 1번 컴퓨터와는 연결되지 않았다는 소리이므로, cc는 1일 때까지만 실행 마지막으로 출력할때는 count에서 1번 컴퓨터를 제외해야 하므로 1 빼고 출력 dfs와 connected components의 개념만 잘 잡혀있었으면 ..