[BOJ] C++ 1941: 소문난 칠공주 - BFS와 백트래킹 섞어 쓰기

1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 예제 YYYYY SYSYS YYYYY YSYYS YYYYY ans : 2 처음에는 일반적인 백트래킹으로 접근했다. 어차피 데이터의 크기가 25로 매우 작고 시간은 2초로 여유롭니 모든 점을 시작점으로 두고 O(25) 재귀식을 상하좌우 중 방문할 수 있다면 방문하는 식으로 짜서 백트래킹으로 구현하였다. 이 방법에서 두 가지 문제점을 발견했는데, 사진으로 보는 게 나을 것 같다. 애초에 백트래킹은 재귀식으로 해야한다는 고정관념에 잘못 접근한 것 같다. 차라리 데이터가 ..

2023.10.30