#알고리즘 #백준 #boj #dfs #그래프탐색 #python #파이썬 #코딩테스트 #항체인식 #boj22352 #실버1 #백준실버 #2차원배열 #배열탐색 #시간복잡도 #알고리즘최적화 #코딩테스트준비 #개발자취준 #취준생 #it취업 #개발블로그 #til #알고리즘스터디 #코테준비1 [Python][BOJ 22352] 항체 인식 [BOJ 22352] 항체 인식 Python 풀이📌 문제 분석N×M 크기의 배열에서 백신 투여 전과 후의 상태가 주어짐백신은 한 번만 투여되며, 투여된 칸과 상하좌우로 연결된 같은 값을 가진 칸들이 모두 동일한 값으로 변경됨주어진 투여 후 상태가 가능한 결과인지 판단해야 함🚨 시행착오처음에는 모든 칸에서 DFS를 시작하고, 가능한 모든 값으로 변경해보는 방식으로 접근시간 복잡도가 O(NM * NM * KNM)로 매우 높았음실제로는 백신이 한 번만 투여된다는 점을 활용하여 최적화 가능했음처음 코드의 문제점불필요하게 모든 칸에서 DFS 시작가능한 모든 값을 시도매번 배열을 원상복구하는 연산 필요어떻게 고쳤나요?투여 전/후가 다른 첫 지점만 찾아서 DFS 실행해당 영역을 투여 후의 값으로 한 번에 변경전체.. 2025. 1. 8. 이전 1 다음