일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
- Stack
- 국민대
- 운영체제
- 국민대학교
- kmu
- machine learning
- 회귀
- 파이썬
- python3
- SQL
- 프로그래머스
- 데이터베이스
- programmers
- Python
- 머신 러닝
- Regression
- GIT
- PANDAS
- instaloader
- C++
- Heap
- gan
- 재귀
- Seq2Seq
- googleapiclient
- OS
- LSTM
- 스택
- db
- 정렬
- Today
- Total
정리 노트
프로그래머스 거리두기 확인하기(Python) 본문
https://programmers.co.kr/learn/courses/30/lessons/81302
코딩테스트 연습 - 거리두기 확인하기
[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1]
programmers.co.kr
이번에도 레벨 2 문제를 골랐다. 문제를 보고 두 가지 생각이 들었다. 모든 경우를 if-elif-else로 푸는 방법과 DFS 또는 BFS를 이용해 푸는 방법이었다. BFS를 활용해서 풀기에는 뭔가 막막한 느낌이 들어서 무지성 if-elif-else 방식을 골랐다.
하나하나 풀어가다보니 나 스스로도 어디를 적고 있는지 헷갈리고, 모든 경우를 생각해야 하다 보니 시간이 너무 오래 지체되었다. 이건 아니다는 생각이 들어 바로 다른 사람의 풀이를 찾아봤다. 역시, 아래 사이트는 BFS 방식을 채택했다.
[프로그래머스] LEVEL2 거리두기 확인하기 (Python)
프로그래머스 알고리즘 풀이
velog.io
완벽히 베끼지는 않고(그래 봤자 98% 똑같은데?) 사소하게 몇 군데를 바꿔서 풀어보았다.
(거의) 다른 사람의 풀이
BFS를 푸는데 queue를 빼놓을 수 없다. 파이썬의 collections 패키지에서 deque를 제공한다. deque의 자세한 사용법은 아래 사이트를 참고하자.
https://docs.python.org/ko/3.8/library/collections.html?highlight=deque#collections.deque
collections — Container datatypes — Python 3.8.13 문서
collections — Container datatypes Source code: Lib/collections/__init__.py This module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple. namedtuple() factory f
docs.python.org
다른 사람의 풀이의 순서를 나열하면 아래와 같다.
- 모든 "P"의 좌표를 BFS의 시작 지점으로 선택한다.
- 각 "P"의 좌표별로 deque를 생성하고, 방문 여부를 초기화한다.
- 탐색 시작점을 기준으로 위, 아래, 왼쪽, 오른쪽 자리를 살핀다.
- 하나의 경우라도 거리두기가 지켜지지 않으면 0을, 아니면 1을 반환한다.
내가 여기서 약간의 변화를 준 구간이 있다.
- BFS 탐색 범위: 다른 사람의 코드대로 가면 맨해튼 거리가 2를 넘어선 범위에 대해서도 탐색을 이어간다.
- 각 자리까지의 거리: 다른 사람의 코드대로면 탐색을 새로 할 때마다 5 * 5의 리스트를 초기화해야 한다.
이를 구현한 코드가 아래의 코드이다.
# 참고: https://velog.io/@sem/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LEVEL2-%EA%B1%B0%EB%A6%AC%EB%91%90%EA%B8%B0-%ED%99%95%EC%9D%B8%ED%95%98%EA%B8%B0-Python
from collections import deque
def check(_place):
start_points = []
for i in range(len(_place)):
for j in range(len(_place[i])):
if _place[i][j] == "P":
start_points.append((i, j))
for s_point in start_points:
bfs_q = deque([s_point])
visited = [[False] * len(_place) for _ in range(len(_place))] # 대기실이 정방형이라 이렇게 가능
visited[s_point[0]][s_point[1]] = True
while bfs_q:
r, c = bfs_q.popleft()
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for i in range(len(dr)):
nr, nc = r + dr[i], c + dc[i]
if 0 <= nr < len(_place) and 0 <= nc < len(_place) and not visited[nr][nc]:
if _place[nr][nc] == "O":
if abs(nr - s_point[0]) + abs(nc - s_point[1]) < 2:
bfs_q.append((nr, nc))
visited[nr][nc] = True
elif _place[nr][nc] == "P":
return 0
return 1
def solution(places):
answer = [check(place) for place in places]
return answer
프로그래머스 채점 서버에서 채점한 결과, 최대 0.15ms, 10.5MB만큼 소모했다.
아예 생각을 못 한 풀이가 아니었어서 살짝 아쉬웠던 문제였다...
'프로그래머스 코딩테스트 연습' 카테고리의 다른 글
프로그래머스 빛의 경로 사이클(Python) (0) | 2022.07.11 |
---|---|
프로그래머스 약수의 개수(Python) (0) | 2022.07.04 |
프로그래머스 수식 최대화(Python) (0) | 2022.07.02 |
프로그래머스 크레인 인형 뽑기(Python) (0) | 2022.07.01 |
프로그래머스 멀쩡한 사각형(Python) (0) | 2022.06.29 |