[IT/코딩테스트] 99클럽 코테 스터디8일차 TIL + BOJ2667

 

오늘의 문제

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

실버1

 

보자마자 이건 dfs 다 !!!  라고 생각했다.

많이 본 스타일의 문제였기 때문에 알 수 있었다. 물론 한번에 잘 풀었느냐? 그건 아님 ㅎㅎ

 

오늘도 역시나~ 권장 시간은 훌쩍 넘겨버렸다. 

1시간 15분이 권장인데 1시간 50분 ㅎ.ㅎ

 

그래도 문제를 보고, '아 이런 식으로 풀어야겠다...!' 라고 생각하고 열심히 코드를 짠 것에 만족(?)한다. 

---

나의 첫 번째 풀이 (성공)

순탄했던 문제 풀이는 아니었어서 생각의 흐름을 적어보려고 한다!

 

1. dfs 로 풀어야겠다!

2. x좌표와 y좌표로 해서 점마다 dfs 를 시키는 걸로 해야겠다.

3. x-1, x+1, y-1, y+1 이렇게 선택해서 이동해야겠다!

4. 좌표가 음수이거나 n 보다 커지면 dfs 함수에서 나오도록 하자

5. graph[x][y] 의 값이 1이면 dfs 를 실행하고 0이면 실행하지 않도록 하자!

6. 단지의 개수를 위한 변수가 있어야할 것 같다.

7. 각 단지에 집이 몇 개인지도 담을 변수가 필요하다.

 

위의 내용을 충족하는 코드를 작성해야겠다고 생각했고 중간에 많은 오류(?)들을 겪으며 최종 완성된 코드는 아래와같다.

중간중간 오류를 겪고 작성에 어려움을 겪던 부분은 주석으로 작성해두었다!

 

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

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


def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1:
        global num # 여기는 글로벌 변수로 해준다. 그래야 참조가 가능
        num += 1
        graph[x][y] = 0 # 탐색을 한 것은 다시 0으로 바꿔준다.
        # 어떻게 하면 한줄로 x, y를 돌 수 있을까.
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False


num = 0
result = 0

for i in range(n):
    for j in range(n):
        if dfs(i, j):
            count.append(num)
            result += 1
            num = 0

count.sort()
print(result)

for i in count:
    print(i)

 

 

 

 

그래도 문제를 보고 어떤 유형인지 파악을 했고!

어떤 로직으로 코드를 짜볼지 그 흐름을 생각했다는 것!

 

에 만족한다 ㅎㅎ

 

앞으로는 오늘 주석을 달았던 부분도 스무스하게 생각할 수 있도록 더 성장해야겠다!

열심히 꾸준하게 공부해보자!

화이팅!