No. 10972
1. Problem
- next permutation (다음 순열) 문제
2. Others' Solutions
- 모든 순열을 구한다음 주어진 수열을 찾은 뒤 바로 다음의 수열을 출력하는 문제 풀이 -> O(N!)
- next permutation (다음 순열) 문제의 대표적인 문제 해결 알고리즘 사용
- 순열의 사전순서는 주어진 요소들을 오름차순으로부터 시작하여 내림차순으로 끝남
- 오름차순으로 순열을 만들면서 오른쪽 끝에서부터 사용할 수 있는 요소를 모두 소진
- 사용 가능한 모든 요소를 소진했다면 back 하여 해당 section 에서 다른 요소 select (오름차순)
- 인접한 요소에서 왼쪽의 요소가 더 크고 오른쪽 요소가 마지막 요소라면 해당 왼쪽 요소는 select 가능한 모든 경우를 다 돌려본 것임
(오름차순으로 생성하는데 자신의 오른쪽 section에 자신보다 큰 값이 없다면 더이상 돌려볼 것이 없음) - 스왑을 하는 경우에는 Decreasing Section의 오른쪽에서 먼저 나타나는 자신보다 큰 값과 스왑
(DS는 내림차순이고 가능한 요소를 select할 때는 오름차순으로 선택해야 하므로 가장 먼저 만나는 큰 수는 그 다음 큰 수임) - 스왑된 경우에도 Decreasing Section은 그대로 내림차순을 유지함
(자신보다 큰 값과 스왑했으니 내림차순은 그대로 유지) - 스왑한 뒤 Decreasing Section은 모든 가능한 경우를 소진한 것이므로 처음으로 돌아가기 위해 오름차순으로 변경해야함
- 내림차순이므로 정렬하지 않고 양끝의 요소들을 서로 swap
① 주어진 순열의 오른쪽에서 시작하여 내림차순이 발견되는 index 찾기
② Decreasing Section(index+1 ~ end)의 오른쪽에서 시작하여 index 값보다 큰 값을 찾음
③ index 값과 큰 값을 swap
④ Decreasing Section(index+1 ~ end)을 오름차순으로 정리
import sys
n = int(sys.stdin.readline())
seq = list(map(int,sys.stdin.readline().rstrip().split()))
flag = False
for i in range(len(seq)-1, 0, -1): # (len(seq)-2, 0, -1)를 하면 n=2 일때 버그
if seq[i-1] < seq[i]: # Decreasing Section 찾기
start = i-1 # Decreasing Section 바로 앞 요소(스왑 기준)의 인덱스를 저장
for j in range(len(seq)-1,start,-1): # Decreasing Section 의 오른쪽에서 부터 start 요소보다 큰 값을 찾음
if seq[j] > seq[start]:
seq[j], seq[start] = seq[start], seq[j] # 찾으면 스와핑 -> 스와핑 된 후에는 여전히 Decreasing Section
break
start = start + 1 # 오름차순할 Section 의 시작 요소
end = len(seq) - 1 # 오름차순할 Section 의 마지막 요소
while(start < end): # 오름차순 정렬
seq[start], seq[end] = seq[end], seq[start]
start += 1
end -= 1
flag = True
break
if flag == True: # 순서가 바뀌었다면
print(*seq)
else: # 마지막 순열이라면 = Decreasing Sequence
print(-1)
3. Learned
- next permutation 문제와 대표적인 해결 방법에 대해 알게됨 (풀이를 외우는 것도 좋음)
- 순열의 생성 규칙에 대해서 더욱 자세하게 알게됨
- 참고 유튜브 1, 참고 유튜브 2
No. 10026
1. Problem
2. My Solution
- DFS 알고리즘을 이용하여 문제 해결
- dfs 함수의 인자로 color 를 넘겨서 확인할 color 정보를 각각 다르게 설정
- R,G 를 탐색한 뒤에는 'v'로 탐색했다는 표시 대신에 'RG'로 다시 초기화
- 각각의 color dfs 탐색에 대한 count 정보를 저장
- 런타임 에러 -> sys.setrecursionlimit(100000) 설정
import sys
sys.setrecursionlimit(100000)
def dfs(x,y,color):
if x < 0 or x > n-1 or y < 0 or y > n-1:
return False
if picture[x][y] == color:
if picture[x][y] == 'R' or picture[x][y] =='G':
picture[x][y] = 'RG'
else:
picture[x][y] = 'v'
dfs(x-1,y,color)
dfs(x+1,y,color)
dfs(x,y-1,color)
dfs(x,y+1,color)
return True
else:
return False
n = int(sys.stdin.readline())
picture = []
count = []
for _ in range(n):
picture.append(list(sys.stdin.readline().rstrip()))
for color in ['R','G','B','RG']:
temp = 0
for i in range(n):
for j in range(n):
if dfs(i,j,color) == True:
temp += 1
count.append(temp)
print(sum(count[:3]), sum(count[2:]))
3. Others' Solutions
- BFS 알고리즘을 이용하여 문제 해결
- BFS 알고리즘은 이웃한(연결된) 노드까지만 탐색 -> 반복
- BFS 알고리즘은 큐를 이용하기 때문에 큐에 중복된 노드(좌표)가 삽입되지 않도록 탐색 후 방문처리 필수
import sys
from collections import deque
def bfs(x,y,color):
queue = deque() # 매번 큐 초기화
queue.append((x,y))
while(queue):
x,y = queue.popleft()
if color == 'R' or color == 'G':
picture[x][y] = 'RG'
else:
picture[x][y] = 'v'
for dx,dy in d: # 인접한 노드 탐색
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < n and picture[nx][ny] == color: # 인접한 노드 탐색 후 방문처리
picture[nx][ny] = 'v'
queue.append((nx,ny))
return True
n = int(sys.stdin.readline())
d = [(-1,0),(1,0),(0,-1),(0,1)]
count = []
picture = []
for _ in range(n):
picture.append(list(sys.stdin.readline().rstrip()))
for color in ['R','G','B','RG']:
temp = 0
for i in range(n):
for j in range(n):
if picture[i][j] == color:
if bfs(i, j,color) == True:
temp += 1
count.append(temp)
print(sum(count[:3]), sum(count[2:]))- 또 다른 방법
- 입력받은 picture를 copy()를 통해서 초기화
- t[x][y] in "RG" 를 통해서 R 혹은 G를 판별
- 만약 RGB만 판단한다면 RGB 각각 전체 돌려보지 않고 bfs 함수에 picture[i][j] color 값을 보냄
from collections import deque
from copy import deepcopy
def bfs(y, x, color):
queue = deque()
queue.append((y, x))
while queue:
y, x = queue.popleft()
for dy, dx in d:
Y, X = y+dy, x+dx
if (0 <= Y < N) and (0 <= X < N) and t[Y][X] in color:
t[Y][X] = '0'
queue.append((Y, X))
N = int(input())
graph = [list(input()) for _ in range(N)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for colors in [['R', 'G', 'B'], ["RG", 'B']]:
t, cnt = deepcopy(graph), 0
for i in range(N):
for j in range(N):
for color in colors:
if t[i][j] in color:
bfs(i, j, color)
cnt += 1
print(cnt, end=' ')
4. Learned
- 그래프 탐색 종류인 DFS & BFS 에 대하여 알게됨 (참고 유튜브)
- DFS 는 일단 가고보는 성격 (방문처리하면서), BFS 는 다음 갈 곳을 일단은 큐에 저장해놓는 성격 (같은 level에서 동일한 노드를 큐에 저장하는 것을 방지하기 위해 방문처리 필수)
- 파이썬에서는 기본적으로 재귀호출의 횟수를 1000번 정도로 제한함 제한을 풀기위해 sys.setrecursionlimit(100000)
