[백준]230223-24 문제풀이

1405. 미친 로봇

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]

n, E, W, S, N = map(int, input().split())
dirs = [E, W, S, N]
def dfs(y, x, direction, visited, cnt):
    global percentage
    if (y, x) in visited:
        temp = 1
        for i in direction:
            temp *= dirs[i] / 100
        percentage -= temp
        return
    if cnt == n:
        return
    for d in range(4):
        dfs(y + dy[d], x + dx[d], direction + [d], visited + [(y, x)], cnt + 1)

percentage = 1
dfs(0, 0, [], [], 0)

print(percentage)

DFS를 이용해서 진행했던 방향들을 저장하면서 탐색하고 진행했던 노드에 돌아오는 경우 저장된 방향들에 대한 확률을 모두 곱해서 전체 확률에서 빼주는 식으로 풀었다. 이상하게 꼬지도 않고 상당히 재밌어서 박살난 멘탈과 자존감을 조금이나마 회복시켜준 문제

2146. 다리 만들기

from collections import deque

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def island():
    global cnt
    while queue:
        qpop = queue.popleft()
        ci, cj = qpop[0], qpop[1]
        find = 0
        for d in range(4):
            ni, nj = ci + dy[d], cj + dx[d]
            if ni < 0 or ni >= N or nj < 0 or nj >= N:
                continue
            if visited[ni][nj]:
                continue
            if nation[ni][nj] == 1:
                nation[ni][nj] = cnt
                queue.append((ni, nj))
                find += 1
        if not find:
            nation[ci][cj] = cnt

def bridge(n):
    global ans
    while queue:
        qpop = queue.popleft()
        ci, cj, bridgelen = qpop[0], qpop[1], qpop[2]
        for d in range(4):
            ni, nj = ci + dy[d], cj + dx[d]
            if ni < 0 or ni >= N or nj < 0 or nj >= N:
                continue
            if nation[ni][nj] == n:
                continue
            if visited[ni][nj]:
                continue
            if nation[ni][nj]:
                if bridgelen < ans:
                    ans = bridgelen
                    break
            visited[ni][nj] = 1
            queue.append((ni, nj, bridgelen + 1))

N = int(input())
nation = [list(map(int, input().split())) for _ in range(N)]
queue = deque()
visited = [[0] * (N + 1) for _ in range(N + 1)]
cnt = 2
for i in range(N):
    for j in range(N):
        if nation[i][j] == 1:
            queue.append((i, j))
            island()
            cnt += 1

ans = 1e4
for i in range(N):
    for j in range(N):
        if nation[i][j]:
            visited = [[0] * (N + 1) for _ in range(N + 1)]
            visited[i][j] = 1
            queue.append((i, j, 0))
            bridge(nation[i][j])

print(ans)

먼저 다리를 놓으면서 같은 섬에 놓지 않도록 각 섬을 구분해줄 수 있는 island 함수를 통해 각 섬의 번호대로 2차원 배열을 수정해줬다. 그리고 bridge 함수를 통해 bfs를 돌리면서 최단 거리를 찾는 방식이었는데... 분명히 맞을텐데 계속 같은 부분에서 틀려서 찾아보니 

5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0

이 반례에서 막혔던 것 같다. 섬의 크기가 2 이상이라고 가정하고 푸니 bfs를 시작하는 원점에서는 섬의 번호를 바꾸지 못한 것. 그래서 조건문을 붙여서 아무것도 찾지 못했을 때도 섬의 번호를 붙이도록 했는데 글 쓰면서 생각해보니 애초에 조건문에 해당하는 조건이 나오면 원점을 먼저 바꾼 후 bridge 함수 바깥으로 cnt++를 빼도 될 것 같다.

 

나름 로직들은 금방금방 떠오르지만 항상 엣지케이스에서 걸리는 걸 보면 아직 많이 두들겨 맞지 않아서 그런 것 같다. 항상 로직이 완벽한지를 먼저 꼼꼼히 체크하고 구현을 시작하는 습관을 의도적으로 들여봐야겠다.