Softeer, 장애물인식프로그램 DFS 재귀활용 cpp 문제풀이

삼성전자 SW역량테스트와 유사하게 현대자동차에서도 Softeer라는 알고리즘 문제푸는 사이트가 생겼습니다.
아직 문제는 별로 없는것 같은데, 현대자동차에서도 삼성전자와 유사하게 역량테스트를 진행하려는 것으로 보입니다.(이미 두번정도 했나봐요.)

오늘은 Softeer 사이트의 문제 중 하나인 장애물인식프로그램을 풀어보겠습니다.

---

Softeer 409, 장애물인식프로그램 문제 개요

소프티어 Softeer, 장애물인식프로그램 문제 링크 ▼

Softeer

장애물인식프로그램 문제는 정사각형 모양의 지도를 입력받고, 상 / 하 / 좌 / 우로 탐색하여 0이 아닌 연결된 장애물(1)영역 별 블록 수를 구하고, 장애물 영역의 수 + 각 장애물 영역의 장애물 수를 오름차순 출력하는 문제입니다.

백준 사이트의 기본 DFS, BFS문제 수준의 난이도로 볼 수 있는 문제입니다.(solved.ac 기준 실버1 정도) Softeer사이트 기준, 별2개 짜리 난이도로 나와있는 문제입니다. 바로 cpp언어로 문제 풀어보겠습니다.

---

Softeer 409, 장애물인식프로그램 문제 cpp 풀이

먼저 cpp 표출 입출력 헤더, 벡터와 인트로정렬(내장 sort함수)를 사용하기 위해 헤더를 선언하고, std 네임스페이스 또한 사전정의했습니다. NxN 그래프의 N값 입력을 받기 위한 변수 N, 또한 선언했습니다. (ans 변수는 시용하지 않았습니다. 무시부탁드려요.)

15 ~ 17행) 그 외에 그래프를 기록할 G, 방문체크용 배열 chk, 정답 기록용 ansList를 벡터로 선언했습니다.
19 ~ 20행) 상하좌우 방문에 사용할 좌표정보 dx, dy와 방문횟수 카운팅용 변수 cnt도 선언했습니다.

DFS, BFS중 저는 DFS로 문제를 풀어보았습니다.

현재 좌표를 기준으로 상하좌우 4방향으로 방문을 시도하는데, 그래프 밖을 나가거나, 장애물이 없는 도로(0)인 경우에는 방문하지 않습니다.

방문하지 않았던 장애물인 경우 카운팅을 하고 깊이우선탐색을 이어나가며, 각 영역의 장애물 수를 카운팅 할 수 있습니다.

메인함수 구현부입니다.

35 ~ 40행) 먼저 입력받은 N에 맞게 G, chk 사이즈를 설정해줍니다. 입력예시의 숫자가 다닥 다닥 붙어있는 형태이므로, "%01d"의 포맷으로 그래프를 입력받아줍니다.

47 ~ 53행) 이후 0 <= i < N, 0 <= j < N의 영역에 대해 차례대로 DFS를 돌려주며 영역의 갯수와 각 영역 별 장애물 수를 ansList에 기록해줍니다. 이후, ansList를 오름차순 정렬 후 정답을 출력해줍니다.

---

Softeer의 2단계 문제, 장애물 인식 프로그램 문제는 기본적인 DFS, BFS 접근이 가능하면 쉽게 풀 수 있는 문제였습니다. 아래는 정답 제출 결과 및 전체소스코드입니다. 다음 문제풀이때 뵙겠습니다. 의견 지적 언제든 환영하구요. 즐거운 하루되세요~

---

제출결과 및 장애물 인식 프로그램 소스코드 링크

Add repo, 장애물인식프로그램_409, DFS, cpp 풀이 · applebuddy/SofteerAlgorithmPS@16c2dce