-
[알고리즘] 백준 1926 그림알고리즘 2022. 8. 6. 00:31728x90
문제
접근
1. dfs 문제로 접근을 하려고 했는데 RecurisionError 즉 재귀적 호출할 시에 문제가 있다고 뜬다.
2. bfs로 접근을 해봤다
3. 전체 그림의 개수, 각 그림의 넓이의 최댓값을 구해야한다.
4. 전체 그림의 개수는 num이라는 변수를 지정하고 bfs문을 한바퀴 돌때마다 +1을 해줘서 출력하면 된다.
4. 그림의 넓이는 cnt라는 변수를 두고 특정 조건안에 돌때마다 1씩 더해가는 식으로 하면 된다 ( 이때 넓이는 *가 아닌 +로 생각)
풀이
틀린 dfs 풀이
n, m = map(int, input().split()) board = [] for i in range(n): board.append(list(map(int, input().split()))) count = [] num = 0 def dfs(x, y): global num if 0 <= x < n and 0 <= y < m and board[x][y] == 1: board[x][y] = 0 num += 1 dfs(x+1, y) dfs(x-1, y) dfs(x, y+1) dfs(x, y-1) return True return False res = 0 for i in range(n): for j in range(m): if dfs(i, j) == True: res += 1 count.append(num) num = 0 # 그림이 하나도 없는 경우는 0 # if len(count) == 0: # count.append(0) print(res) print(max(count) if count else 0)
정답이 된 bfs풀이
# dfs는 재귀관련 에러가 남 (RecursionError) from collections import deque n, m = map(int, input().split()) board = [] for i in range(n): board.append(list(map(int, input().split()))) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] visited = [[False]*m for _ in range(n)] # 전체개수 num = 0 def bfs(x, y): global num # 각 넓이를 위한 개수 cnt = 0 if board[x][y] == 0: return -1 num += 1 cnt += 1 visited[x][y] = True queue = deque() queue.append((x, y)) while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 1 and visited[nx][ny] == False: visited[nx][ny] = True board[nx][ny] = board[x][y] + 1 cnt += 1 queue.append((nx, ny)) return cnt count = [] for i in range(n): for j in range(m): if board[i][j] == 1 and visited[i][j] == False: count.append(bfs(i, j)) print(num) # 그림이 하나도 없는 경우는 0 print(max(count) if count else 0)
'알고리즘' 카테고리의 다른 글
[알고리즘] 백준 1303 전쟁 - 전투 (0) 2022.08.06 [알고리즘] 백준 1388 바닥장판 (0) 2022.08.06 [알고리즘] 프로그래머스 - H-Index (0) 2022.08.03 [알고리즘] 프로그래머스 - 가장 큰 수 (0) 2022.08.03 [알고리즘] 백준 11652 - 카드 (0) 2022.07.28