[백준] 1926번: 그림

 

🔍 문제 읽기

1926번: 그림

 

난이도 : 실버 1

입력	출력
세로 크기 n, 가로 크기 m n*m 크기의 그림 정보	1. 그림의 개수 2. 가장 넓은 그림의 크기 (단, 그림이 0개인 경우 가장 넓은 그림의 크기는 0)

 

💡풀이 

👩‍💻 사용언어 : cpp

❗️[핵심] 다차원 배열에서의 BFS (너비 우선)

1️⃣시작하는 칸을 큐에 넣고 방문 표시

2️⃣큐에서 원소를 꺼내 상하좌우의 인접한 칸에 대해 방문 여부 확인

👉처음 방문한다면 해당 칸을 큐에 넣고 방문 표시

👉방문한 적 있다면 아무것도 안함

3️⃣큐가 텅텅 빌 때 까지 2️⃣를 반복 

 

위 과정의 시간복잡도는?

칸이 N개일 때, 시간복잡도는 O(N)

행이 N개고 열이 M개면, 시간복잡도는 O(NM) 

 

위의 강조된 부분에 주의하여 코드를 작성하자!

 

이 유형에 익숙하다면 골드5 정도의 문제는 풀 수 있다.

완전히 이해하여 더욱 복잡한 조건의 문제를 풀 수 있도록 수련하자.

 

 

 

🧩 코드

✅그림 그리는 board, 방문여부 확인 vis 배열

✅인접칸 확인하는 dx, dy 배열

 

 

다차원 배열을 시각적으로 확인할 수 있는 문제는 비교적 쉽게 접근할 수 있다.