백준 14502 연구소

eprj453·2020년 3월 20일
0

Python과 C++로 풀었으며 C++에서는 queue나 vector를 사용하는 경우가 있습니다.

https://www.acmicpc.net/problem/14502

이 문제의 핵심 포인트는 벽을 무조건 3개만 세운다는 점입니다.

3개를 세웠을 때의 안전영역의 최대가 되는 경우는 곧 바이러스가 가장 적게 퍼지는 경우를 뜻합니다.

2차원 배열의 0(빈 칸) 중 어디에 벽 3개를 세웠을때 바이러스가 가장 적게 퍼지는가를 묻고 있으므로, 모든 경우의 수를 조합으로 전부 따져서 최소값을 구하는 브루트 포스 방법으로 풀어보도록 하겠습니다.

  1. 벽 3개를 치는 경우의 수를 파악한다.
  2. 벽을 쳤을때 바이러스를 퍼트린다.
  3. 바이러스가 퍼진 양으로 답을 갱신한다.

3가지의 단계가 있고, 최대 8*8 배열이므로 브루트포스+백트래킹으로 풀어도 시간초과가 나지는 않겠지만 만약 배열 크기가 크거나 조건이 더 붙는 경우에는 다른 방법을 생각해야겠습니다.

C++

전체 코드입니다.

쪼개서 보겠습니다.
전역변수와 초기 선언입니다.

지도는 2차원 배열로, 바이러스와 안전영역의 위치는 전역 위치에 존재하는 vector에 저장합니다.

Python

예전에 짰던 파이썬도 코드는 비슷합니다. 함수와 구조의 차이가 조금 있지만 위와 개념과 작동방식은 거의 같습니다.

느낀 점

브루트 포스로 문제를 풀었고 실행시간도 그리 길지는 않았지만 다른 좋은 방법이 있는지 생각해봐야겠습니다.

profile
안녕하세요!

0개의 댓글