https://www.acmicpc.net/problem/14466
14466번: 소가 길을 건너간 이유 6
첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다.
www.acmicpc.net
그래프 탐색과 조합론으로 접근했다.
풀이
기본적인 그래프 탐색 문제와의 차별점은 지나가면 안 되는 간선이 주어진다는 점이다. 해당 부분을 어떻게 저장하고 핸들링할지 고민해하는 것이 이번 문제의 핵심.
인접행렬은 상, 하, 좌, 우로 4방향을 따져야 하므로 map[x좌표][y좌표][넘어갈 수 있는 방향 정보] 형태의 3차원 배열을 생성하였다. 즉 N*N*4 배열을 통해 너비우선탐색을 수행하여 해당 소가 방문하지 못하는 좌표에 다른 소가 있다면 문제에서 요구하는 답으로 판정하였다.
문제에서 요구하는 것은 길을 통해 건너야만 만날 수 있는 '쌍'을 찾는 것이니 중복을 없애기 위해 K에서 2개를 뽑는 조합 반복문을 통해 그래프탐색을 수행하였다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [4485] 녹색 옷 입은 애가 젤다지? (0) | 2023.02.05 |
|---|---|
| [3048] 개미 (0) | 2023.02.04 |
| [14464] 소가 길을 건너간 이유 4 (0) | 2023.02.01 |
| [1544] 사이클 단어 (0) | 2023.01.30 |
| [1263] 시간 관리 (0) | 2023.01.29 |