[SWEA 코딩] S/W 문제해결 기본 Contact - PYTHON #1238

소스 코드

def bfs():
    global res_idx
    global res

    temp = [[s,0]]

    while len(temp) != 0:
        idx, cnt = temp.pop(0)

        # cnt 값이 최근에 연락받은 사람의 숫자보다 크면(더 늦게 연락 받으면)
        if cnt > res_idx:
            
            # res_idx값 변경
            res_idx = cnt
            
            # res 값 초기화 후 idx 추가
            res = []
            res.append(idx)

        # cnt와 res_idx이 같으면
        elif cnt == res_idx:
            
            # idx 추가
            res.append(idx)

        for w in range(1,101):
            
            # 연결된 사람이며(연락해야 하는 사람), 상대방이 연락받은 적 없으면(방문 X)
            if board[idx][w] == 1 and visited[w] == 0:
                temp.append([w,cnt + 1])
                visited[w] = 1


    return

for tc in range(1,11):

    # 데이터의 길이 n 시작점 s
    n,s = map(int,input().split())

    # 연락망
    contact = list(map(int,input().split()))

    # 연락 관계 저장
    board = [[0]*101 for _ in range(101)]

    # 방문 확인
    visited = [0 for _ in range(101)]

    # board에 관계 저장
    for q in range(n//2):
        board[contact[2*q]][contact[2*q+1]] = 1

    # 가장 나중에 연락받는 사람들 저장
    res = []

    # 가장 나중에 연락받는 사람의 연락받는 순서
    res_idx = -1

    bfs()

    print('#{} {}'.format(tc,max(res)))

 

---

해결 방법

1. 연락망을 받으면, 이들의 관계를 따로 저장해두기(board은 101 X 101 배열이므로, n의 값이 일정 이상 커지면 for문을 돌면서 연결 관계를 확인하는 것보다 100*100만큼만 확인하는 것이 이득이라 생각함)

 

2. s에서 연락을 시작, 가장 최근에(늦게) 연락받은 순서의 값(cnt)를 저장하고, 연락받는 사람들의 번호를 저장

 

3. visited로 1 -> 4, 4 -> 1 처럼 무한히 반복하거나, 다시 방문할 필요가 없는 경우를 제거

 

4. max로 출력

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.