실버는 무난하게... 아..아니?

#2667번 단지 번호 붙이기 https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

N = int(input())
mat = [[int(x) for x in input()] for _ in range(N)]

visited = [[False for _ in range(N)] for __ in range(N)]

answer = []
tmp = 0


def search(r, c):
    global tmp
    visited[r][c] = True

    state = mat[r][c]
    if state:
        tmp += 1
        if r+1 < N and (not visited[r+1][c]):
            search(r+1, c)
        if 0 <= r-1 < N and (not visited[r-1][c]):
            search(r-1, c)
        if c+1 < N and (not visited[r][c+1]):
            search(r, c+1)
        if 0 <= c-1 < N and (not visited[r][c-1]):
            search(r, c-1)


def print_visited():
    for i in visited:
        print(i)


for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            search(i, j)
            if tmp > 0:
                answer.append(tmp)
                # print(tmp)
                # print_visited()
            tmp = 0

print(len(answer))
for i in sorted(answer):
    print(i)

무난하게 패스 (아마 DFS?..)

 

#4963번 섬의 개수  https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

위 문제에서 진행했던 아이디어에 대각선 방향을 추가하면 무난하게 패스할 수 있는 문제이다.

하지만 방향이 늘어날수록 길어지는 코드가 불만족스러워 구글링했다.

import sys
sys.setrecursionlimit(10000)


def search(r, c, mat, visited):
    global tmp
    visited[r][c] = True

    island = mat[r][c]
    if island:
        tmp += 1
        # bottom
        if r + 1 < h and not visited[r+1][c]:
            search(r+1, c, mat, visited)
        # bottom-right
        if r + 1 < h and c + 1 < w and not visited[r+1][c+1]:
            search(r+1, c+1, mat, visited)
        # bottom-left
        if r + 1 < h and 0 <= c - 1 < w and not visited[r+1][c-1]:
            search(r+1, c-1, mat, visited)
        # up
        if 0 <= r - 1 < h and not visited[r-1][c]:
            search(r-1, c, mat, visited)
        # up-right
        if 0 <= r - 1 < h and c + 1 < w and not visited[r-1][c+1]:
            search(r-1, c+1, mat, visited)
        # up-left
        if 0 <= r - 1 < h and 0 <= c - 1 < w and not visited[r-1][c-1]:
            search(r-1, c-1, mat, visited)
        # right
        if c + 1 < w and not visited[r][c+1]:
            search(r, c+1, mat, visited)
        # left
        if 0 <= c - 1 < w and not visited[r][c-1]:
            search(r, c-1, mat, visited)


def print_visited(visited):
    for i in visited:
        print(i)


while True:

    w, h = map(int, input().split())
    if w > 0 and h > 0:
        mat = [list(map(int, input().split())) for _ in range(h)]
        visited = [[False]*w for _ in range(h)]
        tmp = 0
        answer = []
        for i in range(h):
            for j in range(w):
                if not visited[i][j]:
                    search(i, j, mat, visited)
                    # print(tmp)
                    # print_visited(visited)
                    if tmp > 0:
                        answer.append(tmp)
                    tmp = 0

        print(len(answer))
    else:
        break

import sys
sys.setrecursionlimit(10000)


def search(r, c, mat, visited):
    global tmp

    dr = [1, -1, 0, 0, -1, -1, 1, 1]
    # R,L,B,U,UR,UL,BR,BL
    dc = [0, 0, 1, -1, 1, -1, 1, -1]
    visited[r][c] = True

    island = mat[r][c]
    if island:
        tmp += 1
        for i in range(8):
            nr = r + dr[i]
            nc = c + dc[i]

            if 0 <= nr < h and 0 <= nc < w and not visited[nr][nc]:
                search(nr, nc, mat, visited)


def print_visited(visited):
    for i in visited:
        print(i)


while True:

    w, h = map(int, input().split())
    if w > 0 and h > 0:
        mat = [list(map(int, input().split())) for _ in range(h)]
        visited = [[False]*w for _ in range(h)]
        tmp = 0
        answer = []
        for i in range(h):
            for j in range(w):
                if not visited[i][j]:
                    search(i, j, mat, visited)
                    # print(tmp)
                    # print_visited(visited)
                    if tmp > 0:
                        answer.append(tmp)
                    tmp = 0

        print(len(answer))
    else:
        break

방향을 리스트로 저장해서 간편하게 해결할 수 있었다!..

 

난 왜 이 생각을 못했을까?

 

위 두 문제는 단순히 탐색을 진행하면 됐었다.

그렇게 탐색에 익숙해져있던 나에게 

 

최단거리 문제가 찾아왔다

 

#2178번 미로탐색 https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

위에서 풀었던 문제들과 유사하게 DFS를 활용해 탐색했다.

N, M = map(int, input().split())
mat = [[int(x) for x in input()] for _ in range(N)]
visited = [[False]*M for _ in range(N)]

answer = N*M
def dfs(r, c, step, visited):
    global answer
    if r == N-1 and c == M-1:
        answer = min(answer, step)
        return

    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if 0 <= nr < N and 0 <= nc < M and mat[nr][nc]:
            if not visited[nr][nc]:
                visited[nr][nc] = True
                dfs(nr, nc, step+1, visited)
                visited[nr][nc] = False


visited[0][0] = True
dfs(0, 0, 1, visited)
print(answer)

 

결과는 시간초과.

 

아니 파이썬 재귀 깊이 제한도 안넘었는데 시간부족이라니...ㅠㅜㅠㅜ

다양한 방법으로 시간을 줄여보고자 했지만 힘들었다.

 

구글링 결과 최단거리를 구하는 문제는 BFS가 좋다고 한다.

 

생각해보면 당연하다. 너비 우선 탐색을 하면 최단거리가 나오자 마자 그래프 탐색을 종료시킬 경우

탐색하지 않는 노드들이 남는다.

하지만 깊이 우선 탐색은.. 다 뒤져봐야 하는구나

 

거리 = 깊이 개념으로 이해하면 될 듯 하다.

 

최단거리를 가장 빨리 구할 수 있는 방법은 BFS!!

 

N, M = map(int, input().split())

mat = [[int(x) for x in input()] for _ in range(N)]
visited = [[False]*M for _ in range(N)]


dr = [1, -1, 0, 0]
# B, U, R, L
dc = [0, 0, 1, -1]

queue = [[0, 0]]
while queue:
    r, c = queue.pop(0)

    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]

        if 0 <= nr < N and 0 <= nc < M:
            if mat[nr][nc] == 1:
                queue.append([nr, nc])
                mat[nr][nc] = mat[r][c] + 1

print(mat[N-1][M-1])

심지어 1로 저장되어있는 길을 이동할 때마다 숫자를 더해주는 방법을 택한 코드이다.

이렇게 진행할 경우에

 

1) 지나온 경로의 길이를 저장할 수 있고

2) 탐색한 노드인지 아닌지를 판단할 수 있다. (1이 아닌 경우)

 

난 이 두 가지 기능을 위해서 step변수와 visited 행렬을 생성했는데

 

자괴감에 빠졌다.

 

너무 깔끔하고 좋은 코드라서 당황스러웠다.

 

아직 그래프에 대한 이해가 더딘 듯 하다..