7/1 미경이스터디

Photo by Pietro Mattia on Unsplash

백준 2667 단지번호 붙이기

dfs 코드

n = int(input())
graph = []
answer = []
for _ in range(n):
    graph.append(list(map(int, input())))

def dfs(x,y):
    if y < 0 or y >= n or x< 0 or x >= n:
        return False
    if graph[x][y] == 1:
        global cnt
        cnt += 1
        graph[x][y] = 0
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    return False

result = 0
cnt = 0
for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            answer.append(cnt)
            result+=1
            cnt = 0
answer.sort()
print(result)
for i in range(result):
    print(answer[i])

내가 이해한 룰

1. 위 아래 좌 우 4방향으로 연결된 단지만을 연결됐다고 가정한다.
2. 1은 집이고 0은 집이 없는 곳이다.
3. 연결된 단지의 갯수를 출력하고
4. 각 단지별 집의 갯수를 오름차순으로 정렬하여 출력하면 됨

문제풀이

1. 단지들의 모양을 graph라는 2차원 리스트에 담고
2. dfs함수에 1이 들어오면 True를 반환하고 4방향에 대해 재귀를 실행한다.
3. 이렇게 실행하면 처음 들어온 1과 연결된 모든 집들은 0으로 초기화 되기 때문에
4. graph전체를 순회하는 for문에서 1값은 검사했던 집과 연결되지 않은 집만 남는다.
5. 그래서 dfs값이 True를 반환할 때 마다 result에 1을 더해주면 단지의 수를 구할 수 있다.
6. 이 문제에서는 단지의 갯수를 구하라고 해서 잠깐 버벅였다.
7. cnt를 전역변수 설정을 해줘서 값을 더하고 초기화하기 쉽게 만들었다.
8. 좀 더 많은 유형의 문제를 풀어보면서 답을 구해보아야겠다.

bfs 코드

from collections import deque
n = int(input())
graph = []
answer = []
for _ in range(n):
    graph.append(list(map(int, input())))
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
    
def bfs(graph, x, y):
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0
    cnt = 1
    
    while queue:
        check_x, check_y = queue.popleft()
        for i in range(4):
            nx = check_x + dx[i]
            ny = check_y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx,ny))
                cnt+=1
    return cnt

complex_cnt = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            complex_cnt.append(bfs(graph,i,j))
complex_cnt.sort()
print(len(complex_cnt))
for i in range(len(complex_cnt)):
    print(complex_cnt[i])

문제풀이

1. 마찬가지로 graph를 초기화 해주고
2. queue로 스택을 만들어
3. graph의 값이 1일 때 주변에 연결된 값들을 검사하고
4. 다시 그 값들을 스택에 넣어 검사해 0으로 바꾸어준다.
5. dfs와 로직은 조금 다르지만 결국 비슷하게 graph에 연결되지 않은 1 값만 남도록 바꾸어준다.
6. bfs가 dfs보다 숫자를 구하기 쉬웠는데 스택에 값을 넣을 때 마다 bfs함수 안의 지역변수인 cnt에 1씩 더해주면
7. 지금 검사하고 있는 연결된 집들의 수를 얻을 수 있다.

게임 맵 최단거리

from collections import deque
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    if n == 1 and m == 1:
        return 1
    dx = [0 ,0, 1, -1]
    dy = [1, -1, 0, 0]
    queue = deque()
    queue.append((0, 0))
    while queue:
        check_x, check_y = queue.popleft()
        for i in range(4):
            nx = check_x + dx[i]
            ny = check_y + dy[i]
            if -1< nx < n and -1 < ny < m:
                if maps[nx][ny] == 1:
                    maps[nx][ny] = maps[check_x][check_y]+1
                    queue.append((nx,ny))
    if maps[-1][-1] ==1:
        return -1
    return maps[-1][-1]

내가 이해한 룰

1. 길은 1로 이루어져 있고 벽은 0이다.
2. 캐릭터는 0,0에서 출발해 로우, 칼럼의 끝까지 간다.
3. 끝까지 갔을 때의 캐릭터 이동거리의 최솟값을 구한다.

문제풀이

1. maps를 받아와 row와 column의 길이를 각각 구해준다.
2. row와 column이 각각 1이라면 바로 1을 반환해준다. (처음에 이 로직을 추가하지 않아서 테스트케이스 19번에서 에러가 자꾸났다. 이 로직을 추가하지 않으면 시작점과 목표점이 같을 때에도 -1을 반환하기 때문에 추가해주어야 한다.)
3. 이제 다른 bfs들과 다를게 없다. queue자료구조로 스택을 만들어주고
4. 그 스택에서 나온 x, y 값에 4방향의 값을 미리 더해보고 그 값이 0과 row값, 0과 column값 사이에 있다면 maps의 지금값과 1을 더해 다음값에 더해준다.
5. 마지막으로 maps의 마지막 값을 반환해주면 된다.