[백준] 15주차 스터디 (9663 N-Queen, 14502 연구소, 1753 최단경로)

새싹·2021년 12월 27일
0

알고리즘

목록 보기
29/49

9663 N-Queen

📌문제 링크

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

💡 문제 풀이

이거 분명히 전에 풀었었는데 기억 안나죠?
복습은 정말 중요하다....
심지어 이게 어떤 유형인지 알아내는것도 힘들었다
좌표 하나하나 찍다가 그냥 구글링했다,,,ㅎㅎ

N-Queen은 백트래킹의 대표적인 예제인데, 체스에서 퀸은 가로 세로 대각선으로 범위 제한 없이 이동할 수 있다.
따라서 한 행당 한 개의 퀸만 존재할 수 있으므로 굳이 NxN 배열을 만들 필요 없이 1차원 배열로 표현할 수 있다!

ex) 첫 번째 행에 퀸이 3열에 있다고 하면, col[0]에 3을 저장한다.

여기서 같은 행, 열, 대각선에 있는지 비교하면 되는데

  1. 이미 한 행에 하나의 퀸만 있다고 가정했으니 같은 행일 때는 비교하지 않음
  2. 같은 열일 때 : col[i] == col[depth]일 때
  3. 대각선상에 있을 때 : abs(depth - i) == abs(col[depth] - col[i])
    -> x좌표끼리, y좌표끼리 뺄셈을 했을 때 절댓값이 같은 숫자가 나오면 대각선상에 있음
    ex) (x,y)와 (x+n, y+n)에 퀸이 있다고 했을 때,
    x-(x+n) = y-(y+n) = -n

그리고 퀸을 놓을 수 없다고 판단되면 백트래킹을 수행한다.
(퀸을 놓을 수 없다면 더 진행하지 않고 그 전 단계로 돌아가 다른 루트를 진행한다.)

📋코드

# 9663 N-Queen
# 백트래킹
# 구글링했습니다...

n = int(input())
col = [0] * n
result = 0


def check(depth):
    # 퀸을 놓을 수 있는지 검사
    for j in range(depth):
        if col[depth] == col[j]:
            return False
        elif abs(depth - j) == abs(col[depth] - col[j]):
            return False

    return True


def nqueen(depth):
    global result
    if depth == n:
        result += 1
        return

    for i in range(n):
        col[depth] = i

        if check(depth):
            nqueen(depth+1)


nqueen(0)
print(result)

python3로는 시간초과 떴고, pypy3로 통과했다
그리고 파이썬에서는 자동으로 전역변수 선언이 안 되기 때문에 (배열 제외) 전역변수를 쓰고싶으면 함수 안에서 global로 불러온 뒤 써야 한다

14502 연구소

📌문제 링크

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

💡 문제 풀이

문제를 보고 3187 양치기 꿍 문제가 생각났는데, 알고리즘 분류를 보니 bfs로 푸는 게 맞았다.
문제는 그 이후에 어떻게 풀어야 할 지 모르겠다는 거다...

벽을 도대체 어떤 기준으로 세워야 하는 건지 감이 안 잡혀서 구글링했는데
그냥 빈칸이면 냅다 벽을 세우고 모든 경우의 수를 계산해야 하는 거였다
(입력받는 연구소 크기가 작아서 이렇게 다 계산해도 된다고 함..)

  1. 빈 칸을 발견하면 벽을 세워본다. (이 때 지도를 복사해서 써야함.. 다양한 경우를 확인하는 거기 때문에!!)
  2. 이어서 벽을 2개 더 무작위로 세워본다
  3. 벽 3개를 다 세웠으면 그 상태로 바이러스를 퍼뜨려본다 (bfs)
  4. 바이러스를 퍼뜨린 후 안전 영역을 센다
  5. 최댓값을 비교해가며 result에 저장한다
  6. 1번으로 돌아가서 벽을 다시 허문다 -> 반복
  7. 마지막으로 결과값 출력

처음에 자꾸 결과값이 0이 나와서 왜지?? 했는데 얕은 복사를 써서 그랬다....
이 때 알았다 append가 얕은 복사였다는 걸,,
파이썬에서는 deepcopy 라이브러리를 제공해주니까 넙죽 받아 쓰면 된다

📋코드

# 14502 연구소
import sys
import copy
from collections import deque

n, m = map(int, sys.stdin.readline().split())
arr = []  # 연구소 지도
virus = []  # 바이러스의 위치를 저장할 배열
temp = []  # 벽을 세우고 허물 때 쓸 임시 지도 배열
# 상하좌우 이동
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
# 결과값
result = 0

# 연구소 지도 입력
for i in range(n):
    tmp = list(map(int, sys.stdin.readline().split()))
    # 바이러스의 위치 저장
    for j in range(m):
        if tmp[j] == 2:
            virus.append([i, j])
    arr.append(tmp)


# 바이러스 퍼뜨리기
def spread_virus():
    lab = copy.deepcopy(temp)  # 지도 복사
    q = deque(virus)  # 바이러스 위치 큐 삽입

    # bfs
    while q:
        y, x = q.popleft()  # 바이러스 위치 pop

        # 상하좌우 이동
        for _ in range(4):
            nextY = y + dy[_]
            nextX = x + dx[_]

            if 0 <= nextY < n and 0 <= nextX < m:  # 범위 내
                if lab[nextY][nextX] == 0:  # 빈 칸이면
                    lab[nextY][nextX] = 2  # 바이러스 감염
                    q.append([nextY, nextX])  # 바이러스 큐에 추가

    zero = 0
    # 안전영역(빈 칸) 세기
    for _ in range(n):
        zero += lab[_].count(0)

    # 더 큰 안전 영역의 넓이 저장
    global result
    result = max(result, zero)

    return


# 벽 세우기
# cnt : 벽의 개수
def make_wall(cnt):
    # 벽을 다 세웠으면 바이러스 퍼뜨려보기
    if cnt == 3:
        spread_virus()
        return

    # 벽 3개를 다 안 세웠을 때
    for k in range(n):
        for p in range(m):
            if temp[k][p] == 0:  # 빈칸을 발견하면
                temp[k][p] = 1  # 해당 칸에 벽을 세움
                make_wall(cnt+1)  # 이어서 벽 세우기
                temp[k][p] = 0  # 해당 칸에 벽을 다시 허문다


for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:  # 빈칸을 발견하면
            temp = copy.deepcopy(arr)  # 지도 복사
            temp[i][j] = 1  # 해당 칸에 벽을 세움
            make_wall(1)  # 이어서 벽 세우기
            temp[i][j] = 0  # 해당 칸에 벽을 다시 허문다

print(result)

그냥 돌려봐도 너무 오래 걸려서 python3으로 제출할 엄두도 못 냈다
pypy3로 제출해서 통과!!

1753 최단경로

📌문제 링크

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

💡 문제 풀이

보자마자 어? 이거 분명히..비슷한 유형을 전에 풀었을텐데? 라는 생각이 들었다
하지만 당연하게도 시간이 흘러 까먹었기 때문에... 책을 다시 읽었다

책 예제를 참고하여 다익스트라 알고리즘으로 풀었다.
매번 가장 최단 경로의 정점을 선택해야 하기 때문에 heapq를 이용했다

📋코드

# 1753 최단경로
import sys
import heapq
INF = int(1e9)  # 무한을 의미하는 변수

# 정점의 개수 v와 간선의 개수 e 입력
V, E = map(int, sys.stdin.readline().split())
# 시작 정점의 번호 입력
start = int(input())
# 연결리스트
graph = [[] for i in range(V + 1)]
# 최단 거리 테이블
distance = [INF] * (V + 1)

# 연결 정보 입력
for i in range(E):
    # u에서 v로 가는 가중치 w인 간선이 존재
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append([v, w])


def dijkstra(s):
    q = []
    # (가중치, 정점) 큐에 삽입
    heapq.heappush(q, (0, s))
    distance[s] = 0

    while q:
        dist, now = heapq.heappop(q)

        # 이미 방문한 노드일 경우 continue
        if distance[now] < dist:
            continue
        # 현재 노드의 인접 정점 확인
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, [cost, i[0]])


dijkstra(start)

for i in range(1, V + 1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

이번 주 스터디 후기 : 골드는 골드구나...

1개의 댓글

comment-user-thumbnail
2021년 12월 30일

이거 분명히 전에 풀었었는데 기억 안나죠? 골드는 골드구나...
-> your 맘 = my 맘

답글 달기