Skip to content

Commit 3cbeeba

Browse files
SoniaCompSoniaComp
committed
bitmask, bfs, dfs, backtracking
1 parent f5f8f43 commit 3cbeeba

File tree

5 files changed

+164
-0
lines changed

5 files changed

+164
-0
lines changed

‎BaekJoon/BFS_2573.py‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
import sys
2+
from collections import deque, defaultdict
3+
r, c = map(int, sys.stdin.readline().split())
4+
maps = []
5+
for _ in range(r):
6+
maps.append(list(map(int, sys.stdin.readline().split())))
7+
8+
9+
def bfs(start, maps, visited):
10+
ice = defaultdict(int)
11+
queue = deque()
12+
queue.append(start)
13+
dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
14+
while queue:
15+
y, x = queue.popleft()
16+
visited[y][x] = 1
17+
for dy, dx in dirs:
18+
ny, nx = y+dy, x+dx
19+
if 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
20+
# 주변이 바다인 경우. 근처의 0 개수를 더해준다
21+
if maps[ny][nx] == 0:
22+
ice[(y, x)] += 1
23+
# 주변이 빙산인 경우
24+
elif maps[ny][nx] != 0 and not visited[ny][nx]:
25+
visited[ny][nx] = 1
26+
queue.append((ny, nx))
27+
return ice
28+
29+
30+
def solution(r, c, maps):
31+
time = 0
32+
while True:
33+
visited = [[0 for _ in range(c)] for _ in range(r)]
34+
continent = 0
35+
for y in range(r):
36+
for x in range(c):
37+
# 빙산인 경우
38+
if maps[y][x] != 0 and not visited[y][x]:
39+
# 빙산 좌표별로 근처 0의 개수를 저장한 dictionary를 얻는다
40+
ice = bfs((y, x), maps, visited)
41+
continent += 1
42+
# 빙산이 2개 이상인 경우
43+
if continent > 1:
44+
return time
45+
# 빙산이 사라진 경우
46+
if continent == 0:
47+
return 0
48+
# 빙산 좌표별로 0 개수에 맞게 값을 바꿔준다.
49+
for (y, x), cnt in ice.items():
50+
maps[y][x] = 0 if maps[y][x] < cnt else maps[y][x] - cnt
51+
time += 1
52+
53+
54+
print(solution(r, c, maps))

‎BaekJoon/BFS_backtracking_1987.py‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
import sys
2+
3+
dx = [-1, 0, 1, 0]
4+
dy = [0, -1, 0, 1]
5+
6+
7+
def BFS(x, y):
8+
global answer
9+
# 전역 변수 이용
10+
q = set([(x, y, board[x][y])])
11+
12+
while q:
13+
print('q=')
14+
print(q)
15+
x, y, ans = q.pop()
16+
print(x, y, ans)
17+
for i in range(4):
18+
# 좌우 상하 갈 수 있는지 호ㅘㄱ인
19+
nx = x+dx[i]
20+
ny = y+dy[i]
21+
# 칼럼을 벗어나지 않고, ans 겹치는 알파벳 없는지 체크
22+
if((0 <= nx < R)and (0 <= ny < C) and(board[nx][ny] not in ans)):
23+
q.add((nx, ny, ans + board[nx][ny]))
24+
print('q.add=')
25+
print(q)
26+
answer = max(answer, len(ans)+1)
27+
28+
29+
# 먼저 R, C 행,열 값 입력받음
30+
R, C = map(int, sys.stdin.readline().split())
31+
board = [list(sys.stdin.readline().strip()) for _ in range(R)]
32+
# strip은 공백 삭제!
33+
34+
answer = 1
35+
BFS(0, 0)
36+
37+
print(answer)

‎BaekJoon/DFS_backtracking_1987.py‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
import sys
2+
3+
dx = [-1, 0, 1, 0]
4+
dy = [0, -1, 0, 1]
5+
6+
7+
def DFS(x, y, ans):
8+
global answer
9+
print(x + y + ans)
10+
answer = max(ans, answer)
11+
12+
for i in range(4):
13+
nx = x+dx[i]
14+
ny = y+dy[i]
15+
16+
# index 벗어나지 않는지 체크하고, 새로운 칸이 중복되는 알파벳인지 체크한다
17+
if ((0 <= nx < R) and (0 <= ny < C)) and (board[nx][ny] not in passed):
18+
passed.append(board[nx][ny])
19+
print('append')
20+
print(passed)
21+
DFS(nx, ny, ans+1)
22+
passed.remove(board[nx][ny])
23+
print('remove')
24+
print(passed)
25+
26+
27+
R, C = map(int, sys.stdin.readline().split())
28+
board = [list(sys.stdin.readline().strip()) for _ in range(R)]
29+
30+
answer = 1
31+
passed = [board[0][0]]
32+
DFS(0, 0, answer)
33+
print(answer)

‎BaekJoon/bitmask_2098TSP.py‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
import sys
2+
input = sys.stdin.readline
3+
4+
n = int(input())
5+
# 간선의 weight 표시
6+
adj = [list(map(int, input().split())) for i in range(n)]
7+
# 비트마스크로 n개의 1표시
8+
cpl = (1 << n)-1
9+
# 가장 큰 수
10+
INF = 1 << 30
11+
12+
ans = INF
13+
start = 0
14+
DP = [[0]*(1 << n) for _ in range(n)]
15+
# 다이나믹프로그래밍1: 각 단계의 최적해를 별도의 배열에 저장해둡니다.
16+
# 다이나믹프로그래밍2: 별도의 재귀 함수를 이용해 이 선택을 따라가며 각 선택지를 저장하거나 출력
17+
18+
19+
def solve(cur, visited):
20+
# 종료조건: 모두 방문했을 때
21+
if visited == cpl: # 맨 마지막
22+
return adj[cur][start]
23+
if DP[cur][visited]: # 메모이제이션
24+
return DP[cur][visited]
25+
ans = INF
26+
for i in range(n):
27+
if adj[cur][i] and not visited & (1 << i):
28+
# visited &(1<<i): 1<<i 가 존재하는지
29+
ans = min(ans, solve(i, visited | (1 << i))+adj[cur][i])
30+
# visited |(1<<i): 1<<i를 visited에 추가
31+
DP[cur][visited] = ans # 현재 노드에서 출발해서 모든 노드 방문했을 때
32+
return ans
33+
34+
35+
ans = min(ans, solve(start, 1 << start))
36+
print(ans)

‎BaekJoon/bitmask_practice.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
n= 3
2+
DP = [[0]*(1<<n) for _ in range(n)]
3+
SP = [0]*3
4+
print(SP)

0 commit comments

Comments
 (0)