CHOI

그래프

여러 개체들이 연결되어 있는 자료구조

탐색

특정 개체를 찾기 위한 알고리즘

대표적 문제 유형

1. 경로탐색 유형 (최단거리, 시간)
2. 네트워크 유형 (연결)
3. 조합 유형 (모든 조합 만들기)

DFS(Depth-Firsh Search) 깊이 우선 탐색

• 한 놈만 끝까지 패는 유형

구현 방법

• 재귀함수가 가장 일반적
• 한 가지 방법을 끝까지 다 해보고 다음 방식 동작

BFS(Breadth-First Search) 너비 우선 탐색

• 여러 놈을 한대씩 때리면서 가는 유형

구현 방법

• Queue / LinkedList 사용이 가장 보편적

DFS/BFS 알고리즘 판단 방법

• 자신있는 알고리즘으로 탐색
• DFS의 장점: 하나의 조합을 완성해서 정답과 비교하는 방식임으로 동작 검증이 쉽다
• BFS의 장점: 시간복잡도가 낮다(효율성 TC에 유리)

참조

• https://www.youtube.com/watch?v=BsYbdUnKZ-Y

알고리즘: 완전탐색(Brute Force)

1. 입력: n, m을 입력받아 n 줄의 문자열을 리스트에 저장
2. 8×8 크기의 체스판 모두 탐색 => n-7, m-7 범위에서 모두 탐색
3. 첫 칸이 B, W 인 경우 모두 탐색
4. 2차원 배열 좌표 합의 나머지 규칙으로 인접한 사각형이 같은 색인 경우 칠하는 개수 카운팅
5. B, W 로 시작하는 경우 중 작은 값 n-7, m-7 범위 카운팅 리스트에 저장
6. 출력: 카운팅 리스트에서 최소값을 출력

해결 코드

n,m=map(int,input().split())
board=list()
cnt=list()

for _ in range(n):
    board.append(input())

for i in range(n-7):
    for j in range(m-7):
        blackCase=0
        whiteCase=0
        for a in range(i,i+8):
            for b in range(j,j+8):
                if (a+b)%2==0:
                    if board[a][b]!='B': 
                        blackCase+=1
                    if board[a][b]!='W': 
                        whiteCase+=1
                else:
                    if board[a][b]!='W': 
                        blackCase+=1
                    if board[a][b]!='B': 
                        whiteCase+=1
        cnt.append(min(blackCase,whiteCase))
print(min(cnt))