반응형
문제
https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
풀이
- 딱 보자마자 길찾기 문제다! 라고 생각했음
- 동, 남, 서, 북, 대각선(4방향)을 고려해야겠다고 생각함
- DFS/BFS 둘 다로 풀이할 수 있을 것 같다고 느낌
소스코드
후기
많은 그래프 문제들과 같이 연결 요소의 갯수를 구하는 문제라고 생각한다.
다만 방향이 8가지란 점에서 dx, dy를 8개로 정의를 해줘야 했던 문제였다.
그 외에는 기본적인 BFS/DFS 문제였다고 생각한다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 11725 트리의 부모 찾기 (Swift) (0) | 2022.11.11 |
|---|---|
| [BOJ] 백준 11724 연결 요소의 개수 (Swift) (0) | 2022.11.11 |
| [BOJ] 백준 2644 촌수계산 (Swift) (0) | 2022.11.10 |
| [BOJ] 백준 1012 유기농 배추 (Swift) (0) | 2022.11.08 |
| [BOJ] 백준 2606 바이러스 (Swift) (0) | 2022.11.07 |
