목록깊이우선탐색 (1)

글쓰는공대생의 IT블로그

[백준 - 2267] 단지번호붙이기 (feat. 깊이우선탐색) / C++

출처 => https://www.acmicpc.net/problem/2667 문제 사고의 흐름 ▶ 전형적인 깊이우선탐색 알고리즘을 이용한 문제이다. ▶ 크게 2가지의 포인트를 잡아야 한다. >> 첫 번째 포인트! 1이 발견되면 그 점을 중심으로 왼쪽 오른쪽 위 아래를 조사하는 것. ▶ 나의 풀이에서는 dx[]와 dy[] 배열을 이용하였다. 주위에 있는 x좌표와 y좌표를 nx와 ny로 설정하고 nx=x+dx[i] ny=y+dy[i]로 선언한다. i가 증가할 때마다 x와 y에 값을 더해준다. ▶ 여기서 중요한 것은 아래의 소스코드처럼 i번째의 숫자는 dx[i]와 dy[i]가 달라야 한다. 만약 0으로 같거나 1,-1로 둘이 같게 된다면 이동하지 않거나 대각선으로 이동하기 때문이다. dfs에서의 움직이는 방향..
🖥️ 컴퓨터공학 🖥️/알고리즘 2020. 7. 3. 01:36
이전 Prev 1 Next 다음