짧은 글쓰기
어제 코치님과의 대화에서 하지 말하지 못한 '동료학습'에 대해 느낀점에 대해 쓰고자 한다.
정글에서는 매주 소화할 수 없을 만큼의 과제가 주어진다. 나는 매주 이해가 필요하지만 이해가 느린 편이라 1, 2주차에 해당되는 과제들을 절반도 완수하지 못했다. 여기서 그 이유에 대해 말해보고자 한다.
1. 불가능한 미션을 수행하기 위해 동료들을 활용했어야 했다. 스스로 깨우치는 것이 가장 중요하고 효과적이긴 하지만, 이미 깨우친 동료들에게 도움을 받는 것도 효과적이었을테다. 그러나 나는 매일 주어진 시간이 많았기 때문에 많은 부분을 혼자 깨우쳐보려고 노력했던 것이 결과적으로 나쁜 결과를 낳았다.
2. 내가 잘할 수 있는 것을 위주로 동료학습을 진행했던 것도 문제였다. 잘하는 것이란 결국 좋아하는 것이었는데, 이론적인 부분에서 동료들에게 정보를 공유하다보니 1~3주차에 가장 중요한 알고리즘 문제풀이를 등한시 했다. 나는 정글에 발전하기 위해 왔고, 발전하기 위해서는 내가 가장 무서워하고 고쳐야 할 점을 고쳐야 했지만, 그렇게 하지 않은 것이다. 거기다가 긴 시간을 깨어있다보니 빌어먹을 자기만족(정신승리라 부른다)이 내 발목을 붙잡은 것이다.
남은 일주일간, 혼신을 다해 알고리즘에 집중해야 한다. 늦기 전에 깨달은게 천만다행이다. 코치님 말씀대로 '양치기' 조지자.
이중리스트 탐색(미로, 지도 계열)은 거의 마스터한 것 같습니다. 결국 지도를 구현하고, 방향키로 움직이며 제한 조건에 따라 cnt하거나 요소값을 변경해주면 됩니다. BFS는 다음 위치를 queue에 저장해서 다음 이동할 위치(nx, ny)를 제공합니다. dx,dy 구현에 따라 상하좌우로 움직일 수도, 현재 위치에서 오른쪽으로 시계 반대방향(시계 방향)으로 움직일 수도 있습니다. DFS의 경우 재귀할 때 마다 함수 상단에 있는 것부터 실행하기 때문에 이런 점을 잘 이해해야 합니다. 위쪽에 무엇이 있느냐에 따라 깊이 우선 탐색이 될수도, 넓이 우선 탐색이 될 수도 있습니다.
이중리스트 탐색법(DFS / BFS)
2667 단지 번호 붙이기
정사각형 모양의 지도가 있다.
1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.
여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.
대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다.
지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
출력
3
7
8
9
어제 다룬 미로탐색 문제를 응용할 수 있었던 문제였습니다.
- 추상화
- 주어진 숫자열을 받아 이중 리스트로 지도를 구현합니다.
- dx, dy를 통해 움직일 방향키를 구현합니다.
- (BFS)현재 위치에서 오른쪽, 왼쪽, 위, 아래 한 칸씩을 탐색(이동)하고 1인 곳의 위치 값을 다음 탐색 위치로 정하기 위해 queue에 저장합니다.
3-1. 이동한 뒤 1인 곳에서 위치 값을 매개변수로 전달하여 해당 위치에서 다시 상하좌우를 살핍니다.(하다가 넘어갔다고 걱정하지 않아도 됩니다. 어차피 재귀로 돌아와서 나머지 탐색을 덜한 위치를 다시 탐색하게 됩니다.)- visited를 구현하기 위해 1을 발견한 곳의 요소를 '-1'이나 False로 바꿔줍니다.
-
구체화
- 이중 리스트로 지도를 만들기 위해 길이(입력값) n과 길이만큼 반복할 for문을 작성합니다.
- 상하좌우 방향키를 dx, dy로 만들어줍니다.
- 전체를 탐색해야 하기 때문에(완전 탐색, brute force) 이중 for문으로 i, j 위치를 함수에 전달해줍니다.
- 구역마다의 '1'의 갯수를 세야하기 때문에, count변수를 선언하고 반환해줍니다.
-
구현 코드(BFS)
from collections import deque
n = int(input())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
cnt = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(graph, a, b):
queue = deque()
graph[a][b] = 0
queue.append((a, b))
count = 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n or graph[nx][ny] != 1:
continue
else:
graph[nx][ny] = 0
queue.append((nx, ny))
count += 1
return count
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
cnt.append(bfs(graph, i, j))
cnt.sort()
print(len(cnt))
for i in range(len(cnt)):
print(cnt[i])- DFS
n = int(input())
graph = []
count = []
cnt = [0]
for i in range(n):
graph.append(list(map(int, input())))
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def DFS(x, y):
if x < 0 or x >= n or y < 0 or y >= n:
return False
if graph[x][y] == 1:
cnt[0] += 1
graph[x][y] = 0
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
DFS(nx, ny)
return True
return False
for i in range(n):
for j in range(n):
if DFS(i, j) == True:
count.append(cnt[0])
cnt[0] = 0
count.sort()
print(len(count))
for i in range(len(count)):
print(count[i])1388 바닥 장식
(문제 가독성이 그리 좋지 않습니다..)
형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다.
형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다.
나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다.
기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.
이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다.
만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고,
두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.
기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.
입력값:
4 4
출력값
4
-
추상화
위 문제와 같은 틀입니다. 입력받은 숫자열로 지도를 구현해야 합니다. 그리고 문제의 제한 조건에 따라 '-'일 경우 좌우로만 움직이고, 움직임이 끝났을 때 cnt값을 올려줘야 합니다. '|'의 경우 위아래로만 움직이면 됩니다. 이럴 경우 dx, dy에서 방향키 두개씩 빼주면 됩니다.
그리고 완전 탐색하기 위해 이중 for문을 작성해서 i, j를 현재 x,y값으로 함수로 전달해줍니다.
BFS 함수에서는 visited 처리하고 카운트를 세며 맵을 벗어났는지, 다음 위치가 visit했는지를 확인하며 움직이고, 다음 위치를 반환하기만 하면 알아서 해결해줍니다. -
구체화
움직일 때 마다 graph를 visited처리하고, 그 만큼을 cnt합니다. 다만 단지마다 떨어져있기 때문에 구분하기 위해 cnt 리스트에 담아 구분합니다.
그 외엔 기본틀(지도 구현, 지도에서 상하좌우 이동)과 다르지 않습니다. -
코드
from collections import deque
n = int(input())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
cnt = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(graph, a, b):
queue = deque()
graph[a][b] = 0
queue.append((a, b))
count = 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n or graph[nx][ny] != 1:
continue
else:
graph[nx][ny] = 0
queue.append((nx, ny))
count += 1
return count
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
cnt.append(bfs(graph, i, j))
cnt.sort()
print(len(cnt))
for i in range(len(cnt)):
print(cnt[i])