[프로그래머스](파이썬)FloodFill-Level3-BFS알고리즘 사용
안녕하세요. 그러면 시작하겠습니다...!!입니다. 오늘은 프로그래머스의 FloodFill문제를 풀어보는 시간을 가져보겠습니다.
이 문제는 전형적인 BFS알고리즘을 사용하는 문제로, Level3에 해당하는 어려운 문제입니다. 하지만 아주 많이 응용되는 문제이니 슈도코드를 토대로 잘 따라오시면 되겠습니다.
그러면 시작하겠습니다!
1. 문제소개
2. 슈도코드
목표: 각 좌표를 하나하나 탐색하면서 효율적인 방법을 고안하자.
0. 좌표를 방문했는지 안했는지 체크리스트 생성-->2차원 배열로 체크해줄거임.
-방문했으면 2차원 배열의 원소가 True, 방문안했으면 2차원 배열의 원소가 False.
-큐를 이용한 bfs기법
1. (0,0)=> 처음보는 좌표이므로 큐에 넣음 -queue[(0,0)]
2-a. 큐에서 원소하나 꺼내기 -(0,0)꺼냄 queue[ ]
2-b. 상하좌우로 같은 색인 좌표 큐에 넣기 -queue[(0,1)]
---------------------------------------------------------------
2-a. 큐에서 원소하나 꺼내기 -(0,1)꺼냄 queue[ ]
2-b. 상하좌우로 같은 색인 좌표 큐에 넣기 -queue[(0,2), (1,1)]
---------------------------------------------------------------
2-a. 큐에서 원소하나 꺼내기 -(0,2)꺼냄 queue[(1,1) ]
2-b. 상하좌우로 같은 색인 좌표 큐에 넣기 -같은색 없음
---------------------------------------------------------------
2-a. 큐에서 원소하나 꺼내기 -(1,1)꺼냄 queue[]
2-b. 상하좌우로 같은 색인 좌표 큐에 넣기 -queue[(2,1)]
---------------------------------------------------------------
2-a. 큐에서 원소하나 꺼내기 -(2,1)꺼냄 queue[ ]
2-b. 상하좌우로 같은 색인 좌표 큐에 넣기 -같은색 없음
3. 문제풀이
코드에 대한 설명은 주석에 담아놓았습니다.
4. 알아야할 스킬 셋
1) 호출 함수 만드는 방법
코드를 깔끔하게 코딩하기위해서는 함수를 직접 따로 만들어야할 때가 있습니다.
파이썬에서 함수를 만드는 형식은 다음과 같습니다.
def 함수이름(파라미터): #콜론 무조건 있어야함.
answer = 0
(모듈 또는 반복문 코딩)
return answer
2) List Comprehension(LC)
코드를 보면 방문 여부를 확인하는 2차원 배열이 있습니다. 이러한 것을 List Comprehension이라고 부릅니다.
visited = [[False]*m for _ in range(n)]위 코드의 결과는 n X m의 모든 원소가 False인 2차원 행렬로 나옵니다.
List comprehension은 리스트를 쉽게 생성하기 위한 방법입니다. 이는 파이썬에서 보편적으로 사용되는 기능으로 조금만 응용하면 다양한 조건으로 리스트를 생성할 수 있는 강력한 기능중 하나입니다.
다양한 예시를 보며 LC에 대해 알아보겠습니다.
1) 20까지의 짝수를 출력하기 위해 다음과 같은 LC를 사용할 수 있다
evens = [x * 2 for x in range(11)]
# [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
2) 리스트의 모든 원소값을 정규화 시킨 후 상수값을 더하는 LC
vals = [32, 12, 96, 42, 32, 93, 31, 23, 65, 43, 76]
amount = sum(vals)
norm_and_move = [(x / amount) + 1 for x in vals]
>>> [1.0587155963302752, 1.0220183486238532, 1.1761467889908257, 1.0770642201834861, 1.0587155963302752]
3) 반복문과 if문을 사용한 comprehension
[ i for i in range(30) if i%2 == 0]
>>> [0,2,4,6,8,10,12,14,16,18,20,22,24,26,28]
4) 해시를 사용한 LC
n = 3
servers = [{'a': 0, 'b': 0} for _ in range(n)]
for server in servers:
server['b'] += 1
servers
servers
>>> [{'a': 0, 'b': 1}, {'a': 0, 'b': 1}, {'a': 0, 'b': 1}]5. 시간복잡도
시간복잡도는 n x m
한번도 같은 원소가 큐에 들어가는 일이 없습니다. 따라서 O(n x m)
오늘은 프로그래머스의 FloodFill문제에 대해 알아보았습니다.
진또배기 올림