Baekjoon/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로 받음으로써 배열..