우선 BFS에 필요한 큐를 구현하기 위해서 collections 라이브러리의 deque 자료구조를 사용했습니다.
일반 리스트로도 pop(0) 메소드를 통해 큐의 역할을 구현할 수는 있지만 이 경우 맨 앞의 원소를 제거할 때는 O(n) 시간이 걸린다는 단점이 있어서 deque() 라이브러리를 사용했습니다.
from collections import deque
def solution(maps):
m = len(maps)
n = len(maps[0])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(start_x, start_y, end_x, end_y):
# 거리 정보를 저장하는 배열. 시작점에서 닿을 수 없는 경우 -1의 값을 가짐
dist = [[-1] * n for _ in range(m)]
Q = deque([(start_x, start_y)])
dist[start_x][start_y] = 1
while Q:
cur_x, cur_y = Q.popleft()
for k in range(4):
nx = cur_x + dx[k]
ny = cur_y + dy[k]
# 배열 인덱스를 벗어나는 경우
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
# 벽인 경우
elif maps[nx][ny] == 0:
continue
# 한 번도 방문하지 않은 경우만 큐에 추가
# 최단거리로 방문하려면 같은 블럭을 두 번 이상 방문하는 일은 없어야 한다.
if dist[nx][ny] == -1:
dist[nx][ny] = dist[cur_x][cur_y] + 1
Q.append((nx, ny))
return dist[end_x][end_y]
return bfs(0, 0, m-1, n-1)
인증 백엔드는 세션과도 연관이 있다. 하나의 세션에서는 인증에 사용하는 백엔드를 캐싱해 두고 인증할 때 그 클래스를 사용한다.
django.contrib.auth 모듈의 authenticate()를 호출하면 장고의 모든 인증 백엔드에서 순차적으로 인증을 시도한다.
☑️login() vs authenticate()
인증을 수행한다는 공통점이 있다.
authenticate(): 인증 정보가 유효한지를 한 번 확인한다.
login(): 인증 정보가 유효한지를 확인하고 유효하다면 세션을 만드는 등의 후처리를 한다. 그 결과 한 번 인증된 유저를 여러 번 인증할 필요가 없게 한다.
✅Custom Authentication
기본 인증을 사용하지 않고 새로운 인증 클래스를 만들어서 사용해야 할 때도 있다.
예를 들면 서로 다른 두 앱(django app)의 유저를 통합하거나 할 때, 두 앱에서 모두 사용할 수 있는 인증 클래스가 필요할 것이다.
새로운 인증 백엔드 클래스(Authentication Backend)를 만들기 위해서는 크게 두 가지가 필요하다.
django.contrib.auth.backends 모듈의 BaseBackend 클래스를 상속하는 새 클래스 만들기
해당 클래스에서 두 가지 메소드 구현하기
authenticate: 요청 및 필요시 추가 정보(credentials)를 받아서 인증 되면 user, 아니면 None을 리턴한다.
get_user: user 인스턴스의 pk 값을 받아서 user를 리턴한다.
from django.contrib.auth.backends import BaseBackend
class CustomBackend(BaseBackend):
def authenticate(self, request, credentials=None):
...
def get_user(self, user_id):
...
...
✅Authentication Backend에서 권한(Permissions) 부여하기
BaseBackend 클래스에서는 User 모델 및 UserManager 클래스에서 정의하는 여러 권한 조회 함수들(permission lookup functions)을 사용할 수 있다.
get_user_permissions: 해당 유저가 직접적으로 가진 권한들을 리턴한다.
get_group_permissions: 해당 유저가 속한 그룹이 가진 권한들을 리턴한다.
get_all_permissions: 위의 두 메소드의 합집합을 리턴한다.
has_perm(perm): 유저가 해당 권한을 가지고 있는지를 boolean 값으로 리턴한다.
has_module_perms(module_name): 유저가 해당 모듈(django app)에 해당하는 권한을 하나라도 갖고 있다면 True를 리턴한다.
만약 시행 중 Permission Denied 에러가 리턴되면, 미들웨어처럼 이후의 인증 백엔드를 거치지 않고 에러를 리턴한다.
✅특정 모델 인스턴스에 대해 권한 생성하기
모델 클래스의 Meta 옵션에 permissions 속성을 추가하고, 그 값으로 추가하고 싶은 권한들을 작성한다.
권한들도 DB를 사용하는 경우 하나의 테이블로 맵핑되기 때문에, 이렇게 추가한 권한 값들은 migrate 명령어를 실행한 이후에 생성되므로 그 이후에 사용할 수 있다.
class Task(models.Model):
...
class Meta:
permissions = [
("change_task_status", "Can change the status of tasks"),
("close_task", "Can close the status of tasks"),
]
장고에서 모델과 연결된 DB의 버전을 관리하는 방법이다. migration은 파이썬 파일 형식으로 관리된다.
migration의 특징
실제 DB에서 변경되는 내용이 없어도 migration 파일이 만들어질 수 있다.
어떤 DB에는 적용 가능한 내용이 다른 DB에는 적용 불가능할 수 있다. (MySQL의 경우 PostgreSQL보다 컬럼에 사용하는 max_length 속성의 최댓값이 작다)
직접 migration 파일을 수정할 수 있고 빈 migration 파일을 만들 수도 있다.
transaction 개념이 있는 DB(postgresql, sqlite)의 경우, migration은 하나의 transaction 안에서 실행된다. 그렇지 않은 경우는 transaction 없이 실행되고, 이 경우 migration 도중 failure가 발생하면 rollback이 되지 않는다.
맨 처음 만들어진 migration(initial migration)이 아닌 경우, migration은 다른 migration에 의존한다.
migration이 만들어질 때
python manage.py makemigrations 커맨드를 입력하면 migration 파일이 만들어진다.
migration 파일에는 여러 속성들이 있지만, 그 중에서도 dependencies와 operations가 대표적이다.
dependencies는 해당 migration이 다른 어떤 migration에 의존하고 있는지를 나타낸다.
operations는 해당 migration이 해당 앱의 모델을 어떻게 변형할지를 나타낸다.
makemigrations 명령어에 따라 migration 파일이 만들어지는 원리
장고는 이전에 있던 migration들을 순서대로 실행한다.
현재 모델의 상태와 1번의 과정에서 얻은 모델의 상태를 비교한다. 만약 변화된 점이 없다면 'detected no changes'와 유사한 문구가 뜬다.
2번에서 현재 모델과 migration 파일들을 순차적으로 실행하면서 얻은 모델의 상태에 차이가 있다면, 그 차이점을 바탕으로 migration 파일을 만든다.
migration 관련 명령어들
makemigrations: 위의 과정으로 migration 파일을 만든다.
migrate: makemigrations으로 만들어진 파일이 있는 경우 해당 내용을 실행해서 DB 스키마를 바꾼다. 만약 모델에 변화가 있는데 makemigrations 없이 migrate를 실행한 경우, migration 파일이 만들어지고 그 파일에 대해서 바로 migrate 명령어가 이어서 실행된다.
sqlmigrate: migrate와 똑같이 동작하는데, 다만 동작 과정에서 어떤 SQL문이 실행되는지를 보여준다.
showmigrations: 현재 어떤 migration들이 있는지를 보여준다. migration 파일은 있는데 DB에 반영되지 않은 경우에는 체크 표시가 없고, migration 파일도 있고 DB에 정상적으로 반영된 경우 체크 표시가 있다.
squashmigrations: 기존에 있던 여러 개의 migration 파일을 압축하는 커맨드이다.
기존 여러 개의 migration 파일을 1개 혹은 몇 개로 줄이는 작업이다. 최초 migration부터 입력한 번호까지의 migration을 압축한다고 볼 수 있다. 기존 migration보다 파일의 개수나 operation의 개수는 줄어들지만 DB에 적용되는 내용은 똑같다.
작업 원리
squash 대상이 되는 모든 migration에서 operation을 추출해서 순서대로 정렬한다.
1번 결과에 대해 optimizer를 실행해서, 중복되는 operation은 생략하는 등 operation의 개수를 줄인다. (ex. CreateModel과 DeleteModel이 같이 있다면 두 operation 모두 삭제하기)
2번의 결과를 migration 파일로 만든다.
squashed migration -> normal migration
squashed migration(squashmigration의 결과로 생성된 파일)은 해당 파일의 replace 속성이 있어서 일반 migration과는 달리 "기존의 migration을 대체한" 파일이다.
이 파일이 일반 migration처럼 동작하게 하려면 추가 작업이 필요하다.
squashmigrations 명령어 실행하기
1번의 migration 파일이 대체한 기존 migration 파일들 삭제하기
2번에서 삭제한 migration 파일에 의존하는 다른 파일들의 dependencies 속성을 1번에서 새로 생성된 squashed migration 파일로 수정하기
1번 파일에 표시된 replaces 속성을 삭제하기
fake migration
이미 DB에는 SQL문이 실행되어 테이블과 컬럼이 있으나 장고 migration에서는 반영되지 않았을 때 --fake 옵션을 사용한다.
즉 장고에서 관리하는 migration의 진행 상태만 진행한 것으로 변화시키고, 실제로 DB에 SQL문은 실행하지 않는 것을 fake migration이라고 한다.
initial migration
맨 처음 실행되는 mgiration으로, 다른 migration에 의존하지 않는다.
보통 initial migration은 1개이지만 2개 이상의 initial migration을 만들 수도 있다.
--fake-initial 옵션을 붙이면 이미 DB에서 테이블과 컬럼이 만들어진 경우 초기 migration을 적용하지 않고 스킵할 수 있다. 다만 이 옵션은 적용하려고 했던 initial migration에 선언된 모델이 DB에 존재하는지가 확인되어야 적용할 수 있다. (적용하려는 모델이 없는데 --fake-initial 옵션을 쓸 수는 없다.)
RunPython
기존의 migration 파일을 작성하는 방법이 아니라, python 코드로 DB 내부의 내용을 변경할 수 있다.
(RunPython과 비슷하게는 RunSQL도 있다. 이 경우 SQL문을 직접 장고에서 실행할 수 있다.)
주의 사항
1. RunPython으로 현재 앱이 아닌 다른 앱에 있는 모델에 접근할 경우, migration 파일의 dependencies 속성에다 다음 2가지를 꼭 추가해야 한다.
현재 app의 initial migration
접근하는 다른 앱의 가장 최신 migration
그렇지 않으면 LookupError 에러가 발생한다.
2. RunPython으로 data migration 작업을 할 수 있다.
python manage.py migrate {app_label} --empty 커맨드로 빈 migration 파일을 만든다.
해당 파일의 dependencies 속성에는 해당 앱의 initial migration만 추가한다.
operations에는 migrations.RunPython()을 명시하고, 괄호 안에는 callable(실행 가능한 함수의 이름)을 적는다. data migration 작업을 하는 함수를 만들고 그 함수의 이름을 callable로 적으면 된다.
