2667_단지번호 붙이기

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

2667번: 단지번호붙이기

 

 

 

이전의 bfs와 dfs방식을 이차원 배열로 풀어서 해결해보았더니 성공했다.

 

아래와 같은 순서로 차근차근 해보았다.

 

 

 

1. map에 해당 지도 저장

2. 2차원 그래프와  방문할 곳을 적을 visited 배열 생성

3. 그래프 작성

4. dfs함수 작성

5. map과 visited 값을 비교하면서 dfs 돌리기

6. 나온 정답값을 정렬하고 풀기 (억까조심)

 

 

n = int(input())

map = [ list(map(int,list(input()))) for _ in range(n) ]

graph = [[[] for _ in range(n)] for __ in range(n)]
visited = [ [False] * n for _ in range(n) ]
result = []
count = 1

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


for i in range(n):
    for j in range(n):
        for k in range(4):
            try:
                if  map[i][j] and map[i+dx[k]][j+dy[k]]:
                    if i+dx[k]>=0 and j+dy[k]>=0:
                        graph[i][j].append([i+dx[k],j+dy[k]])
            except:
                continue

def dfs(i,j):
    global count
    visited[i][j] = True
    for x,y in graph[i][j]:
        if not visited[x][y]:
            dfs(x,y)
            count +=1

for i in range(n):
    for j in range(n):
        if not visited[i][j] and map[i][j]:
            count = 1
            dfs(i,j)
            result.append(count)


result.sort()

print(len(result))
for i in result:
    print(i)

 

문제는 2차원 배열에서 상하좌우를 검색하려고 for문을 쓰니까 첫줄 마지막줄, 왼쪽라인 맨우측 라인이 문제가 되어서 try except문을 사용하여 구현해 보았다.

 

 

이전에 공부했던 dx dy를 활용해서 풀어보았는데 잘풀린거 같다!