✅ 문제풀이
🎈 9663 N-Queen
N이 입력값으로 주어지고 구하고자 하는 것은 체스 퀸을 nxn 체스판 위에 서로 공격할 수 없도록 배치하는 경우의 수를 출력하는 것이다.
import sys
input = sys.stdin.readline
n = int(input())
chess = [0] * n
answer = 0
def promising(rows):
for i in range(rows):
if chess[rows] == chess[i] or abs(chess[rows] - chess[i]) == abs(rows-i):
return False
return True
def Nqueen(rows):
global answer
if rows == n:
answer += 1
return
else:
for i in range(n):
chess[rows] = i
if promising(rows):
Nqueen(rows+1)
Nqueen(0)
print(answer)< 풀이 과정 >
백트래킹을 활용한 문제
첫번째 행부터 시작해 퀸을 놓을 수 있는 위치를 지정하고 다음 행으로 이동하며 놓을 수 있는 퀸의 수를 세어가는 문제
- 입력값
퀸을 놓은 자리를 1차원 리스트인 chess를 활용해 저장하였다. row[x] = y인 경우 퀸이 (x,y)위치에 있다. - promising 함수
퀸 위치가 정해진 이후 promising함수를 통해 가지를 늘려간다.
chess[rows] == chess[i] : 같은 열에 위치함
abs(chess[rows] - chess[i]) == abs(x-i) : 위쪽 대각선들에 퀸이 있는 경우 - NQueen 함수
현재 퀸을 놓을 수 있는 위치가 promising하면 다음 퀸을 놓기 위해 NQueen() 재귀 호출
최종적으로 rows == n인 경우 모든 행에 퀸이 위치한 것이므로 마지막 행 + 1을 해주어 결과 리턴
🎈 1987 알파벳
가로 C개, 세로 R개로 된 보드가 있고 각 보드칸에는 알파벳이 적혀있다. 좌측 상단에 말이 시작하여 이동 시 다른 알파벳이 적혀있는 칸으로 이동할 수 있다. 최대 이동할 수 있는 칸 수를 구하는 문제
import sys
input = sys.stdin.readline
rows, cols = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(rows)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 1
def bfs(x, y):
global answer
# 중복 제거를 위해 deque 대신 set 사용
queue = set([(x, y, graph[x][y])])
while queue:
# 말 현재 칸 뽑기
x, y, alpha = queue.pop()
# 말이 지나가는 칸 초기화
answer = max(len(alpha), answer)
for i in range(4):
# 상하좌우 4방향 탐색
nx = x + dx[i]
ny = y + dy[i]
# 주어진 범위 내
if 0<=nx<rows and 0<=ny<cols:
# 다음 칸에 놓인 알파벳이 지금까지 지난 알파벳에 포함이 안되면
if graph[nx][ny] not in alpha:
# set 집합에 추가
queue.add((nx, ny, alpha + graph[nx][ny]))
bfs(0, 0)
print(answer)< 풀이 과정 >
BFS로 경로 탐색을 하는 문제
말이 이동하면서 그동안 써왔던 visited대신 alpha라는 문자열에 다음 문자들을 추가하면서 다음 칸 이동 가능 여부를 체크
deque가 아닌 set를 사용함으로써 중복 제거를 해주어 방문여부를 더 빠르게 알 수 있다.
🎈 2589 보물섬
가로 l, 세로 w로 이루어졌고 L(육지), W(바다)로 알파벳이 구성된 2차원 행렬이 주어진다.
이때 보물은 서로 최단거리로 이동하는 데 있어 가장 멀리 떨어진 육지 두 곳에 나뉘어 묻혀있다.
구하고자 하는 것은 육지 위에 두 칸을 차지하는 보물 간의 거리이다.
from collections import deque
import sys
input = sys.stdin.readline
l, w = map(int, input().split())
maps = [list(input().rstrip()) for _ in range(l)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(i, j):
queue = deque()
queue.append((i, j))
visited = [[0] * w for _ in range(l)]
visited[i][j] = 1
total = 0
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0>nx or l<=nx or 0>ny or w<=ny:
continue
elif maps[nx][ny] == 'L' and not visited[nx][ny]:
visited[nx][ny] = visited[x][y] + 1
total = max(total, visited[nx][ny])
queue.append((nx, ny))
return total-1
answer = 0
for i in range(l):
for j in range(w):
if maps[i][j] == 'L':
answer = max(answer, bfs(i, j))
print(answer)< 풀이 과정 >
BFS로 수차례 풀어 해결하였다.
- 입력값
l, w를 통해 maps를 만들고 방향을 확인하기 위해 dx, dy를 상하좌우로 지정해준다. - bfs 함수
deque를 사용해 현 위치를 deque에 넣어준다. 이때 방문여부를 매 노드마다 확인하기 위해 visited를 만들어주고 현 위치는 1로 처리한다. total 변수를 추가해 시간을 나타낸다.
큐가 빌때까지 반복하며 x, y를 꺼내 다음 위치가 범위를 안벗어나는 선에서 육지를 밟고, 방문하지 않은 곳이라면 visited 값 +1해주고 큐에 다음 위치를 넣어준다. 이때 visited는 칸 수를 의미하므로 최단 경로 중 최대 거리를 뽑기 위해 앞서 선언했던 변수 total의 max값을 찾는다. - 리턴
최종적으로 answer 변수를 선언한 후 2중 for문으로 앞서 만든 maps의 위치가 육지이면 bfs와 answer 중 큰 값을 찾도록 모든 위치에 대해 탐색한다.
🎈 2468 안전 영역
n이 주어지고 N X N의 크기로 지역의 높이정보가 주어진다. 이를 통해 비가 오는 양을 모르는 상황에서, 안전한 영역(그룹)의 최대 개수를 구하는 문제 예시로 아래와 같다.
위 예시의 안전 영역 수는 4개다.
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
# 최고 높이 찾기 위해 변수 선언
max_height = 0
graph = []
for i in range(n):
# 그래프 입력
graph.append(list(map(int, input().split())))
# 최고 높이를 찾기 위해 진행
for j in range(n):
if graph[i][j] > max_height:
max_height = graph[i][j]
# 상하좌우 방향설정
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# bfs 함수 생성 (위치정보, 강수량, 방문여부)
def bfs(i, j, rain, visited):
queue = deque()
# 현위치 큐에 삽입
queue.append((i, j))
# 현 위치 방문처리
visited[i][j] = 1
# 큐에 아무것도 없을 때까지 진행
while queue:
# 큐에서 위치 꺼내고
x, y = queue.popleft()
# 4방향 탐색
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 주어진 그래프 범위 내
if 0<=nx<n and 0<=ny<n:
# 다음 위치한 값이 강수량보다 크고 방문 안한 경우에만 다음 칸으로 이동
if graph[nx][ny] > rain and not visited[nx][ny]:
visited[nx][ny] = 1
queue.append((nx, ny))
# 모든 강수량에 대해 확인하기 위해 answer로 max값 뽑아내기
answer = 0
for i in range(max_height):
# [0, 최고높이-1] 범위 내 확인 위해 강수량마다 방문여부 2차원리스트 생성
visited = [[0]*n for _ in range(n)]
# 이동할 수 있는 안전 영역 숫자 카운팅
group = 0
for j in range(n):
for k in range(n):
# 현 위치한 값이 강수량보다 크고 방문 안한 경우에만 bfs 탐색 진행
if graph[j][k] > i and not visited[j][k]:
bfs(j, k, i, visited)
# 안전 영역이므로 영역 당 + 1
group += 1
# 전체 강수량에 대해 비교 실시
answer = max(answer, group)
print(answer)< 풀이 과정 >
BFS를 활용하여 탐색 실시. 주석을 자세히 달아놔 이해하기 쉽지만, 풀이를 하면 다음과 같다.
- 문제를 읽어보면 비가 얼마나 오는지 주어지지 않았기에 그래프 내 최고높이를 이용해 비가 올 수 있는 양의 범위를 정하였다.
- 이후 BFS함수로 탐색을 실시하였다.
- 모든 강수량에 대해 영역의 수를 비교하기 위해 answer를 만들고 각 강수량의 영역 수는 group으로 체크해 answer와 매 실행이 끝난 이후 비교하는 방식으로 구현하였다.
🎈 2583 영역 구하기
간격이 1인 가로 M 세로 N인 모눈종이가 있고, 이 눈금에 맞추어 k개의 직사각형을 그릴 때 직사각형을 제외한 나머지 부분이 분리된 영역으로 나온다. 입력 값으로 m, n, k를 받고 직사각형 k개의 왼쪽아래 꼭지점 좌표와 오른쪽 위 꼭지점의 좌표를 입력받아 분리된 영역 수와 각 영역의 넓이를 오름차순 정렬하는 문제.
from collections import deque
import sys
input = sys.stdin.readline
m, n, k = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 영역이 칠해진 곳인지 확인위해 사각형 생성
visited = [[0]*n for _ in range(m)]
for _ in range(k):
x1, y1, x2, y2 = map(int, input().split())
# 해당 범위 내 직사각형 존재하므로 색칠하기
for j in range(y1, y2):
for k in range(x1, x2):
visited[j][k] = 1
def bfs(i, j):
queue = deque()
queue.append((i, j))
# 색칠 되지 않은 지역에서 현 위치는 방문처리
visited[i][j] = 1
# 현재 영역 값 1
size = 1
while queue:
큐에서 위치 꺼내어서
x, y = queue.popleft()
# 4방향 탐색
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 주어진 범위 내 만족하며 방문하지 않은 곳이면
if 0<=nx<m and 0<=ny<n and not visited[nx][ny]:
visited[nx][ny] = 1
queue.append((nx, ny))
# 다음 영역 값까지 +1 처리
size += 1
return size
answer = []
for i in range(m):
for j in range(n):
if not visited[i][j]:
answer.append(bfs(i, j))
# 오름차순 정렬
answer.sort()
print(len(answer))
# 리스트 내 원소만 출력
print(*answer, end = ' ')< 풀이 과정 >
k줄만큼 직사각형 각각의 왼쪽 아래 좌표, 오른쪽 위 좌표가 주어졌으므로 일단 이곳은 방문한 곳으로 처리한다.
그 이후 bfs함수를 통해 탐색을 실시하여 size (색칠되지 않은 곳의)를 리턴한다
answer 리스트를 생성해 2중 for문으로 현 그래프 내 방문하지 않은 곳이라면, bfs 탐색을 실시해 결과로 나온 영역의 값을 answer리스트에 삽입한다.
이후 오름차순 정렬한 영역의 수와 요소 값을 출력한다.
To be a DataScientist