코딩테스트를 공부하기 위해 알고리즘 문제들을 풀어보았습니다.
코딩테스트 공부는 처음이라서 그래도 이해하기 쉬운 파이썬 언어로 진행을 하였고, DFS & BFS를 공부하면서 풀어보기 좋은 기본적인 문제들을 선정하여 풀어보았지만 아직 처음이라 그런지 많이 어려워서 다른분들이 해결하신 코드들을 많이 참고하면서 공부를 한 후에 제 방식대로 주석을 달아보면서 풀이해보았습니다!
문제 사이트 : https://www.acmicpc.net/problem/1926
문제해석을 간단하게 하자면 N*M크기의 도화지에 그려진 그림의 갯수와 그 그림들 중 가장 큰 넓이를 가지는 그림의 넓이값을 출력하는 문제입니다.
저는 이 문제를 해결하기 위해서 BFS를 사용하여 풀이하였고 코드는 아래와 같습니다.
우선 대략적인 큰 틀을 잡고 시작하는게 좋을 것으로 판단하여 도화지(pic), 그림의 갯수(cnt), 그림의 넓이를 담을 배열(result) 변수 선언을 먼저 해주었습니다.
그 다음 반복문을 통하여 그림을 그리게 하면서 BFS를 동작하게 구성을 하였습니다. 상하좌우를 설정해주고, 초기좌표설정을 0으로 해주었고, 초기넓이도 1로 해주었습니다. 이후 4방향으로 검사를 해 준후에 도화지 안에 위치하거나 아직 방문을 하지 않았다면 방문처리를 해주게끔 작성하였습니다. 이후에 그림이 그려져있다면 BFS를 탐색시작하여 그림의 갯수를 증가시켜가면서 그림의 갯수와 그림의 최대넓이값을 출력해주는 것으로 코드를 마무리 하였습니다.
백준 사이트에서도 문제없이 잘 통과되네요ㅎㅎ
감사합니다!
