음료수 얼려 먹기
문제
N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다
입력
첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
4 5
00110
00011
11111
00000
출력
한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
3
문제 해결 아이디어
DFS/BFS로 해결 가능
- 얼음 얼릴 수 있는 공간이 상하좌우로 연결되어 있다고 표현 가능 → 그래프 형태로 모델링 가능
내가 시도한 코드
def dfs(x, y):
graph[i][j] = 1 # 현재 노드 방문 처리
tx, ty = x, y # 이동 위치 체크용 .. (이거 필요 없음)
for i in range(4): # 상하좌우 살피기
if x+dx[i] >= 0 and x+dx[i] < M and y+dy[i] >= 0 and y+dy[i] < N:
if graph[x+dx[i]][y+dy[i]] == 0: # 빈 곳이면
graph[x+dx[i]][y+dy[i]] = 1 # 여기를 dfs로 재귀 호출 했어야 함
tx = x+dx[i] # 필요 x
ty = y+dy[i] # 필요 x
x, y = tx, ty # 필요 x
return x, y # 필요 x
N, M = map(int, input().split())
graph = [list(map(int, input())) for i in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
result = 0
for i in range(N):
for j in range(M):
if graph[i][j] == 0:
i, j = dfs(i, j) # 필요 x 그냥 dfs(i, j) 호출해주면 됨
result += 1
print(result)
-
재귀 호출 생각 안 하고 풀어서 틀렸음 ....
어쩌다 상하좌우 살피고 그 위치를 전달해줄 생각을 했는지 나도 잘 모르겠지만 .. 재귀 호출만 하면 현재 위치의 상하좌우뿐만 아니라 상하좌우의 상하좌우까지, 즉 연결된 모든 부분을 쭉 탐색할 수 있는 걸 캐치하지 못했다는 거 티나쥬ㅜㅜ
-
아 그리고 00110 처럼 붙어서 들어오기 때문에
list(map(int, input()))으로 들어온 문자열 자체에 map 해줘야 함! 습관적으로 .split() 추가해서 계속 인덱스 오류났다 ^^;
코드 - DFS
DFS 활용
-
특정 지점의 상하좌우 살펴본 뒤, 주변 지점 중 값이 0이면서 아직 방문하지 않은 지점 있으면 해당 지점 방문
-
방문한 지점에서 다시 상하좌우 살피며 방문을 진행하는 과정 반복 시, 연결된 모든 지점 방문 가능
-
모든 노드에 대하여 1~2번 반복하며 방문하지 않은 지점 수 카운트
def dfs(x, y):
if x < 0 or x >= N or y < 0 or y >= M:
return False
if graph[x][y] == 0: # 방문하지 않은 노드면
graph[x][y] = 1 # 방문 처리
# 상하좌우 살펴보고 재귀적으로 방문 처리
dfs(x-1, y)
dfs(x, y-1)
dfs(x+1, y)
dfs(x, y+1)
return True
return False # 방문한 노드면 return False
N, M = map(int, input().split())
graph = [list(map(int, input())) for _ in range(N)]
print(graph)
result = 0
for i in range(N):
for j in range(M):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result)(0, 0)부터 시작해서, 값이 0인 위치를 찾았으면 그 지점을 기준으로 상하좌우를 살피는데, 상하좌우에 값이 0인 위치가 있으면 그 위치의 값을 1로 변경해서 방문 표시를 해줌
이때 함수가 재귀적으로 호출되면서 원래 기준 위치의 상하좌우 노드 각각의 상하좌우를 또 살피게 되므로, 서로 연결된 노드들이 모두 1로 바뀌면서 연결된 하나의 모양 전체에 방문 처리가 되는 것
따라서 기준 위치에서 연결되어 있는 모든 노드를 탐색한 후에 return True에 걸려서 True 값이 전달되고, result 값은 하나만 올라가게 됨
코드 - BFS
BFS 활용
-
값이 0인 위치에 대해서, 현재 위치 정보를 원소로 하는 큐를 생성하고 현재 위치의 값은 1로 변경함으로써 방문 표시를 해두고
-
큐가 빌 때까지 현재 위치를 기준으로 BFS를 진행
위치 정보 x, y를 pop 해서 얻어내고, 현재 위치의 상하좌우 중에 값이 0인 위치를 큐에 집어 넣어줌
큐가 빌 때까지 하므로 dfs와 마찬가지로 넣은 위치의 상하좌우를 또 살피게 되고 결국 연결된 모든 부분 탐색 완료
-
탐색이 끝나면 True 값 return 해서 카운트 증가시키거나,
현재 위치에서 탐색이 끝나면 1을, 값이 0이 아니었다면 0을 return 해줌으로써 bfs 함수값 자체로 카운트 1 증가하는 효과를 줄 수 있음
from collections import deque
def bfs(x, y):
if graph[x][y] == 0:
q = deque([(x, y)])
# 현재 위치를 기준으로 BFS 탐색
while q:
x, y = q.popleft() # 현재 위치
graph[x][y] = 1 # 방문 처리
# 상하좌우 탐색
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 0:
q.append((nx,ny))
return 1
return 0
N, M = map(int, input().split())
graph = [list(map(int, input())) for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
result = 0
for i in range(N):
for j in range(M):
result += bfs(i, j)
print(result)-
큐 초기화를
q = deque((x, y))으로 해버려서x, y = q.popleft()에서
cannot unpack non-iterable int object오류 남안전하게 하는 방법은
q = deque()로 빈 덱 만들어두고q.append((x, y))로 추가하는 방법도 있음
-
dx, dy를 밖에서 선언 안 하고
for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:이런 식으로 사용도 가능
미로 탈출
문제
N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
입력
첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
5 6
101010
111111
000001
111111
111111
출력
첫째 줄에 최소 이동 칸의 개수를 출력한다.
10
문제 해결 아이디어
BFS 활용
상하좌우로 연결된 모든 노드로의 거리가 1로 동일하므로, (0,0) 지점부터 BFS 수행하여 모든 노드의 최단 거리 값을 기록하면 해결 가능
이동한 경로의 값을 이전 경로의 값 + 1 해주면 거리 값이 됨
내가 시도한 코드: 틀림
from collections import deque
def bfs(x, y):
if graph[x][y] != 0:
q = deque([(x, y)])
while q:
x, y = q.popleft()
for i in range(2):
nx, ny = x+dx[i], y+dy[i]
if 0<=nx<N and 0<=ny<M and graph[nx][ny]!=0:
graph[nx][ny] = graph[x][y]+1
q.append((nx, ny))
N, M = map(int, input().split())
graph = [list(map(int, input())) for _ in range(N)]
dx = [1, 0]
dy = [0, 1]
result = 0
for i in range(N):
for j in range(M):
bfs(i, j)
print(graph[N-1][M-1])-
어차피 최단 거리니까 오른쪽이랑 아래로 가는 경우만 챙겨준다고 생각했음
그래서 dx, dy를 오른쪽, 아래인 경우만 설정해서 이동할 수 있는 위치에 대해서 해당 경우들로만 큐를 업데이트 해줌
-
이전 값에다가 +1 한 값으로 배열 내 값들이 계속 변경되니까 이동할 수 있는 조건으로 값==1이 아닌 값!=0을 해줬고 ..
조건에서 제시된 입출력에 대해서 내 코드의 그래프는 아래랑 같다 ㅜㅜ
(4, 0)이 방문되지 않으면서 다시 1로 리셋돼서, (4, 5)의 값이 (3, 5)+1인 9가 되는 게 아니라 (4, 4)+1인 6이 돼버렸음..!
[1, 0, 1, 0, 1, 0]
[2, 3, 4, 5, 6, 7]
[0, 0, 0, 0, 0, 8]
[1, 2, 3, 4, 5, 6]
[2, 3, 4, 5, 6, 7]코드 - BFS
from collections import deque
def bfs(x, y):
q = deque([(x, y)])
while q:
x, y = q.popleft()
# 현재 위치에서 상하좌우 확인
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
# 미로 찾기 공간 벗어난 경우 무시
if nx < 0 or nx >= N or ny < 0 or ny >= M:
continue
# 벽인 경우 무시
if graph[nx][ny] == 0:
continue
# 방문하지 않은 노드면 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
q.append((nx, ny))
# 원하는 위치까지의 최단 거리 반환
return graph[N-1][M-1]
N, M = map(int, input().split())
graph = [list(map(int, input())) for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
print(bfs(0, 0))범위를 벗어나거나 벽인 경우 무시하고, 그렇지 않으면서도 방문하지 않은 노드이면 이전 위치 값 + 1로 거리 값을 갱신해줌
최종 그래프를 출력해보면 다음과 같음
[3, 0, 5, 0, 7, 0]
[2, 3, 4, 5, 6, 7]
[0, 0, 0, 0, 0, 8]
[14, 13, 12, 11, 10, 9]
[15, 14, 13, 12, 11, 10]- 과정을 좀 더 자세하게 표로 나타낸 블로그 확인!
Source
이코테 2021 강의 몰아보기
