스스로 고민하고 답을 보지 않고 구현을 해보았는데요

카카오 코테 6주 합격! 실전 파이썬 코딩테스트

목표 문제: 문제 접근법

해결된 질문

작성

수정됨

# 1012

T = int(input())

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

for _ in range(T):
    M, N, K = map(int, input().split())
    graph = [[0] * M for i in range(N)]

    st = []
    seen = set()
    # seen.add((0, 0))

    for i in range(K):
        x, y = map(int, input().split())
        graph[y][x] = 1
        st.append([y, x])

    cnt = 0
    while st:
        cur = st.pop()


        for i in range(4):
            x = dx[i] + cur[0]
            y = dy[i] + cur[1]

            if not (0 <= x < N and 0 <= y < M):
                continue
            if (x, y) in seen:
                continue
            if graph[x][y] == 0:
                continue

            st.append([x, y])
            seen.add((x, y))

        if (cur[0], cur[1]) in seen:
            continue
        else:
            seen.add((cur[0], cur[1]))
        cnt +=1

    print(cnt)

값이 처음 구현 햇을때 제대로 안나오길래

원래는 cur를 for i in range(4) 위에서 seen에 찍어줬었는데 -> 실패

그래서 cur를 방점을 찍어주듯이 주변을 다 돌고 자신을 seen에 찍게 했더니 통과가 되서

혹시 코드에 조언해주실 수 있는지 질문드립니다!

코딩-테스트 알고리즘 소프트웨어-설계 data-structure

답변 2

헤이밥

지식공유자

코드는 깔끔하고 좋습니다!

다만, seen 이라고 이름 지은 이유가 해당 좌표를 dx, dy를 통해 발견한 적이 있다면 '본 적있다(seen)'고 해서 seen인데, 이름을 visited로 바꿔주면 변수명과 데이터 내용이 좀 더 일치할 것 같네요

코드 깔끔하고 너무 좋습니다 ㅎㅎ

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

감스트의웃음노예님께서 작성하신 코드를 보니, DFS(깊이 우선 탐색) 방식으로 문제를 해결하려는 의도가 잘 드러납니다. 코드가 잘 작성되어 있으며, 동작 원리를 간단히 설명드리겠습니다.

그래프 초기화: 전처리 단계에서 주어진 좌표에 대하여 graph에 배추 위치를 기록하고 있습니다.
DFS 탐색: 반복문 내에서 스택을 이용한 DFS로 모든 배추 위치를 탐색하고, 이미 방문한 위치는 seen에 기록하며 다시 탐색하지 않습니다.
카운팅: 새로운 뭉텅이(새로운 DFS 탐색의 시작점)를 만날 때마다 cnt를 증가시켜 전체 영역의 수를 구합니다.

현재 코드에서 수정할 부분은 많지 않아 보입니다. 다만, 코드의 효율성과 가독성을 조금 더 높이기 위한 몇 가지 팁을 드리겠습니다.

조건문 조합 최적화: if 문을 통해 탐색할 때 여러 조건들을 하나의 복합 조건으로 묶어 활용하면 반복적인 continue를 줄일 수 있습니다.
주석 추가: 각 단계가 어떤 로직을 수행하는지 간단한 주석을 추가하면 가독성을 높이는 데 도움이 될 것입니다.

관련된 문제 해결 방법에 대한 커뮤니티 사례를 참조할 수 있습니다: 그룹 단어 체커 - 백준 1316번 관련 문의드립니다..

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

스스로 고민하고 답을 보지 않고 구현을 해보았는데요