[1일 3알고리즘] Day7

1. 덧칠하기

https://school.programmers.co.kr/learn/courses/30/lessons/161989

프로그래머스

# [Lv.1] 덧칠하기
def solution(n, m, section):
    paint = 0
    ans = 0
    # wall = [i for i in range(n)]
    for n in section:
        if n > paint:
            paint = n + m - 1
            ans += 1
    return ans

위와 같이 풀이하였다. 처음에는 배열을 만들고 DP를 활용하는 문제인줄 았았는데, 쉬운 풀이가 있었다.

 

2. 미로 탈출

https://www.acmicpc.net/problem/14923

14923번: 미로 탈출

(대체 무슨 자신감으로 이 문제를 도전한건지 모르겠다)

from collections import deque

n, m = map(int, input().split())
hx, hy = map(int, input().split())
ex, ey = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]

visited = [[[False] * 2 for _ in range(m)] for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y):
    queue = deque([(x, y, 0, 0)])  # 시작 위치와 거리는 0, 마법 사용은 안함으로 시작
    visited[x][y][0] = True

    while queue:
        x, y, dist, magic = queue.popleft()

        if x == ex - 1 and y == ey - 1:
            return dist

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if maze[nx][ny] == 0 and not visited[nx][ny][magic]:
                    visited[nx][ny][magic] = True
                    queue.append((nx, ny, dist + 1, magic))
                elif maze[nx][ny] == 1 and not magic and not visited[nx][ny][1]:
                    visited[nx][ny][1] = True
                    queue.append((nx, ny, dist + 1, 1))

    return -1


print(bfs(hx - 1, hy - 1))

처음에 마법 부분을 global 변수로 선언하여 if 문을 통해 마법을 사용하려고 했지만, 아예 틀렸었다. 다른 분들의 풀이를 보고 아예 뜯어 고치게 되었는데, 우선 [x][y][magic] 형태로 배열을 선언하여 마법 사용 여부를 확인하였다. 이 문제는 추후 다시 풀어야겠다.

 

3. 단지번호붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

위 문제에서 호되게 반성하고 쉬워보이는 문제로 넘어왔는데, 

n = int(input())

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

num = 2


def dfs(x, y):
    global num
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    # 1 부분인 집을 이을때 해당 배열에 1 2 3으로 변수 추가.
    if graph[x][y] == 1:
        graph[x][y] = num
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)
        return True
    return False


total = 0
house_cnt = []

for i in range(n):
    for j in range(n):
        if dfs(i, j) == True:
            house_cnt.append(sum(row.count(num) for row in graph))
            num += 1

print(len(house_cnt))  # 집 집합의 총 개수
house_cnt.sort()  # 집 집합별 집의 수를 정렬하여 출력

for count in house_cnt:
    print(count)

이 풀이에서도 단지를 계산하는 간단한 방법을 제대로 생각해내지 못해서 지피티의 도움을 받았다. DFS 와 BFS 를 제대로 풀기 위해 많은 노력이 필요할 것 같다.